请注意本题特殊的时间限制。
给定整数 $n,m,\mathrm{mod}$。
对于一个 $1\sim n$ 的排列 $p=(p_1,p_2,\ldots,p_n)$,定义长度为 $n-1$ 的数组 $b(p)$。对于每个 $1\le i<n$:
- 在所有满足 $i<j<n$ 且 $[p_{i+1}>p_i]\ne[p_{j+1}>p_i]$ 的下标 $j$ 中,取最小的一个,令 $b_i(p)=j$;
- 如果不存在这样的 $j$,则令 $b_i(p)=n$。
其中,$[S]$ 表示:若命题 $S$ 成立,其值为 $1$;否则为 $0$。
称一个长度为 $n-1$ 的整数数组 $a$ 是 好的,当且仅当同时满足:
- 对于每个 $1\le i<n$,都有 $i+1\le a_i\le\min(n,i+m)$;
- 存在至少一个 $1\sim n$ 的排列 $p$,使得 $a=b(p)$。
求不同的好数组的数量,对 $\mathrm{mod}$ 取模。
只要两个数组在至少一个位置上的值不同,就认为它们不同。同一个数组即使对应多个排列,也只计数一次。
输入格式
一行三个整数 $n,m,\mathrm{mod}$。
每个测试点只有一组输入数据。
输出格式
输出一行一个整数,表示不同的好数组的数量对 $\mathrm{mod}$ 取模的结果。
样例
样例输入 #1
4 3 100000000
样例输出 #1
6
样例解释 #1
六个好数组分别为:
$$(2,3,4),\ (2,4,4),\ (3,3,4),\ (3,4,4),\ (4,3,4),\ (4,4,4).$$
样例输入 #2
5 3 1000000007
样例输出 #2
17
样例解释 #2
共有 $17$ 个好数组。例如,排列 $p=(3,1,2,5,4)$ 对应好数组 $a=(3,5,5,5)$。
对于 $i=1$,$p_2<p_1$、$p_3<p_1$,而 $p_4>p_1$,所以满足条件的最小下标为 $j=3$,即 $a_1=3$。
样例输入 #3
20 7 1000000007
样例输出 #3
575731297
数据范围
对于所有测试点,保证:
$$1\le m<n\le1000,\qquad m\le250,\qquad 10^8\le\mathrm{mod}\le10^9+7.$$
不保证 $\mathrm{mod}$ 是质数。
本题共有 $16$ 个子任务。每个子任务采用捆绑测试:只有通过该子任务的全部测试点,才能获得该子任务的分数。各子任务独立计分。
| 子任务 | 分值 | 限制 | 单点时限 |
|---|---|---|---|
| 1 | 4 | $n\le 9$ | 1 秒 |
| 2 | 6 | $n\le 12$ | 5 秒 |
| 3 | 2 | $m=1$ | 1 秒 |
| 4 | 5 | $m=2$ | 1 秒 |
| 5 | 7 | $m\le 8$ | 5 秒 |
| 6 | 5 | $m\le 32$ | 5 秒 |
| 7 | 4 | $m\le 100$ | 10 秒 |
| 8 | 4 | $m\le 160$ | 10 秒 |
| 9 | 5 | $n\le 25$ | 5 秒 |
| 10 | 5 | $n\le 60$ | 5 秒 |
| 11 | 8 | $m=n-1$ | 5 秒 |
| 12 | 6 | $m=n-2$ | 5 秒 |
| 13 | 4 | $n-m\le 8$ | 5 秒 |
| 14 | 5 | $n\le 300$ | 10 秒 |
| 15 | 10 | $n\le 600$ | 15 秒 |
| 16 | 20 | 无额外限制 | 15 秒 |