AT_arc020_4.[ARC020D] お菓子の国の旅行

糖果国是一个狭长的国度，拥有 $N$ 个城镇，这些城镇沿直线排列，编号从 $1$ 到 $N$。相邻城镇之间有道路连接，城镇 $i$ 和城镇 $i+1$ 之间的路长为 $D_i$。在糖果国，出行只能通过这些道路进行。对于城镇 $a$ 和 $b$（$a < b$），从城镇 $a$ 到城镇 $b$ 的距离，以及从城镇 $b$ 到城镇 $a$ 的距离，都是从 $D_a$ 到 $D_{b-1}$ 之间道路长度的总和。每个城镇都有一个独特的糖果专卖店，每家店只出售一种独特的糖果。当访问某个城镇时，必须购买该店出售的糖果。

住在蚂蚁王国的 Ant 先生非常喜爱甜食和数字 $M$。他计划在糖果国旅行，并恰好购买 $K$ 种不同的糖果。为了选择访问顺序，他想先计算一下，总的移动距离是 $M$ 的倍数的旅行方案有多少种。需要注意的是，旅行过程中不允许绕远路，并且可以选择任何城镇作为起始和结束点。同一个城镇不能重复访问。此外，移动过程中经过而不驻留的城镇不算作访问过。

请为 Ant 先生编写一个程序，计算移动距离总和为 $M$ 倍数的旅行方案数量。因为结果可能非常大，请输出对 $1000000007(10^9+7)$ 取模的结果。

输入以以下格式给出：

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

• 第一行输入三个整数：表示城镇数量的 $N\ (2 \leq N \leq 100)$，Ant 先生钟爱的数字 $M\ (1 \leq M \leq 30)$，以及他计划购买的糖果种类数 $K\ (2 \leq K \leq 10$ 且 $K \leq N)$。
• 接下来的 $N-1$ 行，每行一个整数 $D_i\ (1 \leq D_i \leq M)$，表示城镇 $i$ 到城镇 $i+1$ 的道路长度。

输出满足条件的旅行方案数量，对 $1000000007(10^9+7)$ 取模。输出结果末尾应有换行。

部分分数

有部分分数可得：

• 如果所有满足 $N \leq 12$ 的测试用例均正确，则可获得 $30$ 分。

示例解释 1

有以下 $6$ 种方案：

• 城镇 $1 \rightarrow 3 \rightarrow 2$ 的访问顺序。
• 城镇 $2 \rightarrow 3 \rightarrow 1$ 的访问顺序。
• 城镇 $2 \rightarrow 1 \rightarrow 4$ 的访问顺序。
• 城镇 $4 \rightarrow 1 \rightarrow 2$ 的访问顺序。
• 城镇 $2 \rightarrow 3 \rightarrow 4$ 的访问顺序。
• 城镇 $4 \rightarrow 3 \rightarrow 2$ 的访问顺序。

示例解释 2

因为结果可能很大，记得对 $1000000007(10^9+7)$ 取模。

本翻译由 AI 自动生成