问题描述

糖果国是一个非常细长的国家。糖果国有 $N$ 个城镇，这些城镇沿一条直线排列，从端到端编号为 $1$ 到 $N$。相邻城镇之间有道路，连接城镇 $i$ 和城镇 $i+1$ 的道路长度为 $D_i$。由于糖果国只有这些道路可供移动，对于城镇 $a$ 和 $b$（$a < b$），从城镇 $a$ 到城镇 $b$ 的移动距离和从城镇 $b$ 到城镇 $a$ 的移动距离都是 $D_a + D_{a+1} + ... + D_{b-1}$。每个城镇都有一家糖果专卖店，每家专卖店售卖一种与其他城镇不同的糖果。当访问某个城镇时，必须在该城镇的糖果专卖店购买糖果。

蚂蚁国的居民 Ant 先生喜欢甜食和数字 $M$。Ant 先生要去糖果国旅行，他想要购买恰好 $K$ 种糖果。为了决定访问哪个城镇的糖果专卖店，以及访问的顺序，Ant 先生决定首先计算移动距离的总和为 $M$ 的倍数的访问城镇方式有多少种。但值得注意的是，移动不可以绕远路。另外，首次访问的城镇和最后一次访问的城镇可以是任意城镇。同一个城镇不能被访问两次。请注意，在移动途中经过某个城镇并不等同于访问该城镇。

请为 Ant 先生编写一个程序，计算移动距离的总和为 $M$ 的倍数的访问城镇方式的数量。由于答案可能非常大，输出请取模 $1000000007(10^9+7)$。

输入

输入以以下格式从标准输入中给出。

$N$ $M$ $K$ $D_1$ $D_2$ : $D_{N-1}$

• 第一行包含三个整数，分别表示糖果国的城镇数 $N (2 ≤ N ≤ 100)$，Ant 先生喜欢的数 $M (1 ≤ M ≤ 30)$ 和 Ant 先生打算购买的糖果种类数 $K (2 ≤ K ≤ 10$ 且 $K ≤ N)$。
• 第二行到第 $N-1$ 行是相邻城镇之间的道路长度。其中，第 $i$ 行给出了连接城镇 $i$ 和城镇 $i+1$ 的道路长度 $D_i (1 ≤ D_i ≤ M)$。

部分分

本问题设有部分分。

• 对于满足 $N ≤ 12$ 的测试用例，如果输出正确，则得到 $30$ 分。

输出

请输出答案取模 $1000000007(10^9+7)$ 后的结果，并在末尾换行。

输入示例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)$。