题目描述

有 $n$ 个编号为 $1$ 到 $n$ 的盒子，每个盒子的容量均为 $t$，现在有 $k$ 次操作，对于第 $i$ 次操作，可以选择在编号为 $[L_i,R_i]$ 的盒子中放入一个小球，且需保证放完小球后盒子不能溢出。求本质不同的可行操作序列的方案数。两种可行操作序列本质不同当且仅当存在某一次操作二者选择的区间不同。

输入格式

输入仅一行三个整数 $n, k, t$。

输出格式

输出仅一行一个整数表示答案对 $1011110011$ 取模后的结果。

样例

3 2 1

10

以下是 $10$ 种方案：

• $[1, 1], [2, 2]$；
• $[1, 1], [2, 3]$；
• $[1, 1], [3, 3]$；
• $[1, 2], [3, 3]$；
• $[2, 2], [1, 1]$；
• $[2, 2], [3, 3]$；
• $[2, 2], [3, 3]$；
• $[3, 3], [1, 1]$；
• $[3, 3], [1, 2]$；
• $[3, 3], [1, 2]$。

15 6 4

458177764

$x^n+y^n=z^n$。

子任务

对于所有数据，均满足 $1\le n,k,t\le 40$，$t\le k$。