C. Егор и друзья
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Егор с друзьями гуляли по лесу, всего, включая Егора, гуляло n человек. Очень скоро перед ними оказалась река. Ребята сразу же захотели перебраться через реку, тем более, что возле берега, к которому подошла компания стояла лодка. Известно, что эта лодка вмещает людей, суммарным весом не более k килограмм.

Егор тут же выписал на листок бумаги список весов всех людей из его компании, включая свой вес. Оказалось, что каждый человек весит либо 50, либо 100 килограмм. Сейчас Егору нужно знать, за какое минимальное количество переправ на лодке через реку вся компания сможет оказаться на другом берегу. При переправе в лодке обязательно должен быть хотя бы один человек. При переправке в лодке может сидеть любое (ненулевое) количество человек, но их суммарный вес не должен превышать k.

Так же Егора заинтересовал вопрос: сколько существует способов переправить всех людей на другую сторону за минимальное количество переправ на лодке. Два способа считаются различными, если при какой-либо переправе множество людей находящихся в лодке отличается.

Помогите Егору с этой задачей.

Входные данные

В первой строке записано два целых числа n, k (1 ≤ n ≤ 50, 1 ≤ k ≤ 5000) — количество людей, включая Егора, и вместительность лодки. В следующей строке записаны n целых чисел — веса людей. Вес человека — это либо 50 килограмм, либо 100 килограмм.

Можете считать, что Егор и друзья пронумерованы некоторым образом.

Выходные данные

В первую строку выведите целое число — минимальное количество переправ. Если невозможно переправить всех людей на другой берег, то выведите целое число -1.

Во вторую строку выведите остаток от деления количества способов переправить людей за минимальное количество переправ на число 1000000007 (109 + 7). Если невозможно переправить всех людей на другой берег, то выведите число 0.

Примеры
Входные данные
1 50
50
Выходные данные
1
1
Входные данные
3 100
50 50 100
Выходные данные
5
2
Входные данные
2 50
50 50
Выходные данные
-1
0
Примечание

В первом тесте Егор гуляет один и соответственно требуется только одна переправа через реку.

Во втором тесте нужно действовать по следующему плану:

  1. переправить двух людей весом по 50 килограмм;
  2. переправить одного человека весом 50 килограмм обратно;
  3. переправить человека весом 100 килограмм;
  4. переправить человека весом 50 килограмм обратно;
  5. переправить двух людей весом по 50 килограмм.

Суммарно выходит 5 переправ. В зависимости от того, какого человека выбрать на шаге 2, получаются два различных способа.