有一天,格雷格和他的朋友们在森林里散步。总共有 n 个人在行走,包括格雷格。很快他就发现自己来到了一条河边。大伙儿当即决定过河。幸运的是,河岸边有一艘船,就在他们站的地方。我们知道,船最多可以承载总重量为k公斤的人。
格雷格立即拿出一张纸,列出了他小组中所有人(包括他自己)的体重。原来,每个人的体重要么是50公斤,要么是100公斤。现在格雷格想知道船需要过河最少多少次才能将整个团队运送到对岸。这艘船至少需要一个人才能将其从一侧岸带到另一侧。当船过河时,它可以载有任意非零数量的乘客,只要他们的总重量不超过 k。
格雷格还想知道,有多少种方法可以用最少的乘船次数将每个人运送到另一边。如果在某些骑行过程中船上有不同的人,则两种方式被认为是不同的。
帮助格雷格解决这个问题。
输入
第一行包含两个整数 n, k (1 ≤ n ≤ 50, 1 ≤ k ≤ 5000) — 人数(包括 Greg)和船的重量限制。下一行包含 n 个整数——人们的体重。一个人的体重要么是50公斤,要么是100公斤。
您可以考虑以某种方式对 Greg 和他的朋友进行索引。
输出
在第一行打印一个整数 - 最小骑行次数。如果不可能将所有人运送到另一家银行,请打印整数 -1。
在第二行中,打印最少乘车次数中运送人员的方式数除以数字 1000000007 (109 + 7) 后的余数。如果不可能将所有人运送到另一家银行,请打印整数 0。
示例
输入 #1
1 50 50
输出 #1
1 1
输入 #2
3 100 50 50 100
输出 #2
5 2
输入 #3
2 50 50 50
输出 #3
-1 0
注意
在第一个测试中,格雷格独自行走,因此,他只需要乘车过河一次。
在第二次测试中,您应该遵循以下计划:
1.运输两个50公斤。人们;
2.运输一件50公斤。人回来了;
3.运输1个100公斤。人;
4.运输一件50公斤。人回来了;
5.运输两个50公斤。人们。
总共 5 次骑行。根据第 2 步中选择的人,我们可以得到两种不同的方法。