Егор с друзьями гуляли по лесу, всего, включая Егора, гуляло n человек. Очень скоро перед ними оказалась река. Ребята сразу же захотели перебраться через реку, тем более, что возле берега, к которому подошла компания стояла лодка. Известно, что эта лодка вмещает людей, суммарным весом не более k килограмм.
Егор тут же выписал на листок бумаги список весов всех людей из его компании, включая свой вес. Оказалось, что каждый человек весит либо 50, либо 100 килограмм. Сейчас Егору нужно знать, за какое минимальное количество переправ на лодке через реку вся компания сможет оказаться на другом берегу. При переправе в лодке обязательно должен быть хотя бы один человек. При переправке в лодке может сидеть любое (ненулевое) количество человек, но их суммарный вес не должен превышать k.
Так же Егора заинтересовал вопрос: сколько существует способов переправить всех людей на другую сторону за минимальное количество переправ на лодке. Два способа считаются различными, если при какой-либо переправе множество людей находящихся в лодке отличается.
Помогите Егору с этой задачей.
Выходные данные
В первую строку выведите целое число — минимальное количество переправ. Если невозможно переправить всех людей на другой берег, то выведите целое число -1.
Во вторую строку выведите остаток от деления количества способов переправить людей за минимальное количество переправ на число 1000000007 (109 + 7). Если невозможно переправить всех людей на другой берег, то выведите число 0.
Примечание
В первом тесте Егор гуляет один и соответственно требуется только одна переправа через реку.
Во втором тесте нужно действовать по следующему плану:
- переправить двух людей весом по 50 килограмм;
- переправить одного человека весом 50 килограмм обратно;
- переправить человека весом 100 килограмм;
- переправить человека весом 50 килограмм обратно;
- переправить двух людей весом по 50 килограмм.
Суммарно выходит 5 переправ. В зависимости от того, какого человека выбрать на шаге 2, получаются два различных способа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 50
50
|
1
1
|
|
2
|
3 100
50 50 100
|
5
2
|
|
3
|
2 50
50 50
|
-1
0
|