CF295C.Greg and Friends

One day Greg and his friends were walking in the forest. Overall there were n people walking, including Greg. Soon he found himself in front of a river. The guys immediately decided to get across the river. Luckily, there was a boat by the river bank, just where the guys were standing. We know that the boat can hold people with the total weight of at most k kilograms.

Greg immediately took a piece of paper and listed there the weights of all people in his group (including himself). It turned out that each person weights either 50 or 100 kilograms. Now Greg wants to know what minimum number of times the boat needs to cross the river to transport the whole group to the other bank. The boat needs at least one person to navigate it from one bank to the other. As the boat crosses the river, it can have any non-zero number of passengers as long as their total weight doesn't exceed k.

Also Greg is wondering, how many ways there are to transport everybody to the other side in the minimum number of boat rides. Two ways are considered distinct if during some ride they have distinct sets of people on the boat.

Help Greg with this problem.

一天，格雷格和他的朋友们在森林中行走。总共有 $n$ 个人（包括格雷格）在行走。很快，他们来到了一条河边。大家立刻决定渡过这条河。幸运的是，河边恰好停着一艘船，位置就在众人所在之处。已知这艘船最多能承载总重量为 $k$ 千克的人。

格雷格立即拿出一张纸，列出了小组中所有人（包括他自己）的体重。结果发现，每个人的体重恰好是 $50$ 千克或 $100$ 千克。现在，格雷格想知道：将整组人全部运送到对岸所需的船最少往返次数是多少？船每次从一岸驶向另一岸时，至少需要一人驾船。在船横渡河流的过程中，船上可载任意非零人数，只要其总重量不超过 $k$ 千克即可。

此外，格雷格还想知道：在达到最小往返次数的前提下，有多少种不同的运送方案？若在某一次航行中，船上所载人员集合不同，则认为这两种方案是不同的。

请帮助格雷格解决这一问题。

The first line contains two integers n, k (1 ≤ n ≤ 50, 1 ≤ k ≤ 5000) — the number of people, including Greg, and the boat's weight limit. The next line contains n integers — the people's weights. A person's weight is either 50 kilos or 100 kilos.

You can consider Greg and his friends indexed in some way.

第一行包含两个整数 $n$、$k$（$1 \leq n \leq 50$，$1 \leq k \leq 5000$）——分别为人数（包括 Greg）和船的重量限制。
下一行包含 $n$ 个整数——各人的体重。每个人的体重为 $50$ 千克或 $100$ 千克。

你可以以某种方式对 Greg 及其朋友们进行编号。

In the first line print an integer — the minimum number of rides. If transporting everyone to the other bank is impossible, print an integer -1.

In the second line print the remainder after dividing the number of ways to transport the people in the minimum number of rides by number 1000000007 (109 + 7). If transporting everyone to the other bank is impossible, print integer 0.

第一行输出一个整数——完成运输所需的最少渡河次数。如果无法将所有人运送到对岸，则输出整数 $-1$。

第二行输出在最少渡河次数下，所有可能的运输方案数对 $1000000007$（即 $10^9 + 7$）取模后的余数。如果无法将所有人运送到对岸，则输出整数 $0$。

In the first test Greg walks alone and consequently, he needs only one ride across the river.

In the second test you should follow the plan:

1. transport two 50 kg. people;
2. transport one 50 kg. person back;
3. transport one 100 kg. person;
4. transport one 50 kg. person back;
5. transport two 50 kg. people.

That totals to 5 rides. Depending on which person to choose at step 2, we can get two distinct ways.

在第一个测试用例中，Greg 独自过河，因此他仅需一次渡河。

在第二个测试用例中，应遵循以下方案：

1. 运送两名体重为 50 kg 的人；
2. 将一名体重为 50 kg 的人送回；
3. 运送一名体重为 100 kg 的人；
4. 将一名体重为 50 kg 的人送回；
5. 运送两名体重为 50 kg 的人。

总共需要 5 次渡河。根据步骤 2 中选择哪一名 50 kg 的人返回，我们可以得到两种不同的方案。