問題文
糖果之国是一个非常狭长的国家。在糖果之国 有 N 个城镇,从末端开始排成一条直线。 它们的编号最大为 1 从 N 。邻近城镇之间有公路; i 和镇 i+1 连接我们的道路长度是 D_i 。这些道路是糖果之乡唯一的交通工具,所以 a, b (a < b) 关于城镇 a 卡拉町 到 b 的距离和城镇 b 卡拉町 到 a 行驶的距离是 D_a + D_{a+1} + ... + D_{b-1} 。每个城镇都有一家糖专卖店。 1 每家糖专卖店都出售与其他城镇不同的糖。 1 我们销售不同类型。当你访问某个城镇时,你必须从该城镇的糖专卖店购买糖。
蚂蚁先生,一只住在蚂蚁王国的蚂蚁,喜欢糖果和数字。 我喜欢 M 。 Ant目前正在前往糖果之国旅行。 K 我想购买不同类型的糖。为了决定去哪个城镇以及以什么顺序参观糖店,蚂蚁首先计算在糖果之地行驶的总距离。 我决定计算访问一个城镇的方式有多少种,它是 M 的倍数。不过,我们在城镇之间旅行时不会走很远的弯路。另外,你访问的第一个城镇和你访问的最后一个城镇都很好。切勿两次访问同一个城镇。请注意,在城镇之间途经城镇并不意味着您已经访问过该城镇。
对于蚂蚁来说,在糖果之地行驶的总距离是 请编写一个程序来查找访问城镇的方式数量,该数量是 M 的倍数。然而,答案可能是一个非常大的数字,所以 请输出除以1000000007(10^9+7) 后的余数。
入力
输入将以以下格式从标准输入给出。
N M K
D_1
D_2
:
D_{N-1}
- 1 行包含一个整数,表示糖果之国的城镇数量。 N (2 ≦ N ≦ 100) 和 Ant 最喜欢的整数 M (1 ≦ M ≦ 30) 和一个表示蚂蚁金服正在考虑购买的糖类型数量的整数。 来自行 K (2 ≦ K ≦ 10 和 K ≦ N) 用空格分隔。
- 2 从行 N-1 线给出了连接邻近城镇的道路长度。其中 i 镇 i 和镇 表示连接 i+1 的路径长度的整数 D_i (1 ≦ D_i ≦ M) 给出。
部分点
针对此问题设置了部分分数。 如果所有满足
- N ≦ 12 的测试用例都得到正确回答, 给出 30 点。
出力
答案 除以 1000000007(10^9+7) 后的余数 1 行输出。在输出末尾插入换行符。
入力例1
4 4 3 2 1 3
出力例1
6
下面 6 有两种方法。
- 町 1 → 町 3 → 町 2 参观糖专卖店。
- 町 2 → 町 3 → 町 1 参观糖专卖店。
- 町 2 → 町 1 → 町 4 参观糖专卖店。
- 町 4 → 町 1 → 町 2 参观糖专卖店。
- 町 2 → 町 3 → 町 4 参观糖专卖店。
- 町 4 → 町 3 → 町 2 参观糖专卖店。
入力例2
15 5 10 5 5 5 5 5 5 5 5 5 5 5 5 5 5
出力例2
897286330
答案可能是一个非常大的数字,所以 除以1000000007(10^9+7) 时不要忘记计算余数。