题目描述

Pesho 正在对一个长度为 $N$ 的序列进行加密，其中 $1$ 到 $N$ 每个整数都恰好出现一次。他使用如下算法：

1. 将原序列中的每个数 $X$ 替换为第 $X$ 个质数。
2. 随机选择一个正整数 $K$，满足 $K \le N$。
3. 考虑所有连续子序列。对于每个长度至少为 $K$ 的连续子序列，记下其中最小的 $K$ 个数的乘积。
4. 设上一步记下的不同乘积个数为 $P$。
5. 最终密码记为 "N K P"。

下面看一个例子，Pesho 如何对序列 $\{4,1,3,2\}$ 加密：

1. 前 $4$ 个质数分别是 $2,3,5,7$。因此原序列中的元素被替换为：

   • $4$ 替换为第 $4$ 个质数 $7$；
   • $1$ 替换为第 $1$ 个质数 $2$；
   • $3$ 替换为第 $3$ 个质数 $5$；
   • $2$ 替换为第 $2$ 个质数 $3$。

   得到新序列 $\{7,2,5,3\}$。

2. 随机选择一个数 $K$。设 $K=2$。

3. 所有连续子序列为：

   $\{7\}$，$\{2\}$，$\{5\}$，$\{3\}$，$\{7,2\}$，$\{2,5\}$，$\{5,3\}$，$\{7,2,5\}$，$\{2,5,3\}$，$\{7,2,5,3\}$

   删去所有长度小于 $K=2$ 的子序列，并对剩余每个子序列求其中最小 $K=2$ 个数的乘积：

   • $\{7,2\} \to 2\times 7=14$
   • $\{2,5\} \to 2\times 5=10$
   • $\{5,3\} \to 3\times 5=15$
   • $\{7,2,5\} \to 2\times 5=10$
   • $\{2,5,3\} \to 2\times 3=6$
   • $\{7,2,5,3\} \to 2\times 3=6$

   因此写下的数为 $\{14,10,15,10,6,6\}$。

4. 不同的数有四个：$\{6,10,14,15\}$，所以 $P=4$。

5. 得到密码 "4 2 4"。

Pesho 很快发现，这个算法比他原先想象的要“强”得多：仅凭密码并不总能唯一确定原序列。

请你编写程序 crypto，给定一个密码，计算有多少个可能的原始序列。答案对 $1\ 000\ 000\ 007$ 取模。

输入格式

输入的第一行包含三个正整数 $N$、$K$ 和 $P$。

输出格式

输出一个整数，表示密码为 "N K P" 的原始序列个数。答案对 $1\ 000\ 000\ 007$ 取模。

数据范围

• $1 \le K \le N \le 400$
• $1 \le P \le 1\ 000\ 000\ 000$

子任务

• $20\%$ 的测试满足 $N \le 10$
• $60\%$ 的测试满足 $NK \le 30000$

样例 1

输入

3 2 3

输出

2

样例解释

序列 $\{1,3,2\}$ 和 $\{2,3,1\}$ 都会被加密成 "3 2 3"。

样例 2

输入

4 2 4

输出

12

样例解释

满足条件的序列有：

$\{1,2,4,3\}$、$\{1,3,2,4\}$、$\{1,4,2,3\}$、$\{2,1,4,3\}$、$\{2,3,1,4\}$、$\{2,4,1,3\}$、$\{3,1,4,2\}$、$\{3,2,4,1\}$、$\{3,4,1,2\}$、$\{3,4,2,1\}$、$\{4,1,3,2\}$、$\{4,2,3,1\}$。