题目思路

如果没有这些限制，就是一个经典的爬楼梯问题，我们使用动态规划解决。状态$dp(i)$为:从山底走到第$i$层的所有可能方案数。

但是我们有$p,k$的限制，所以转移形如:

我们可以暴力的直接转移，得到$O(nm^2)$ 的 $dp$ 但是时间不允许，会超时。只能拿一部分分数。

题目内容

小红是一个热爱户外运动的人，他周末经常约朋友一起登山。华光林山清水秀，景色宜人，让他感到非常愉悦。他喜欢在登山的过程中欣赏美景，感受大自然的魅力。同时，他也喜欢挑战自己，尝试攀登更高的山峰。

小红登山时每一步可以选择向上爬一个台阶或者多个台阶，如果登山时选择的台阶不同，则为一种爬山方案。

小红想知道，华光林的每座山各有多少种不同的爬山方案(输出结果对 $10^9 +7$ 取模)。

输入描述

第一行，三个整数 $N$ 、 $P$ 和 $K$ 分别代表山的个数 $N$ ，小红一次最高能爬的高度 $P$ 以及小红一次最多能跨越的台阶数 $K$ 。

( $1 \le N \le 10$ ， $1 \le P\le 1,000$ ， $1 \le K \le 1,000$ )

接下来 $N$ 行，每行的第一个整数 $M_i$ 表示第 $i$ 座山一共有 $M_i$ 个台阶，接下来有 $M_i$ 个整数，分别表示每个台阶的高度 $H_j$

( $1 \le M_i \le 10,000, 1\le H_j \le 1,000$)。

输出描述

输出 $N$ 行，每行一个整数，表示第 $i$ 座山小红可以选择的登山方案数目。

样例

样例一：

输入

3 3 2
4 1 1 1 1
4 2 2 2 2
5 2 2 2 3 4

输出

5
1
0

备注

如果某一台阶 $H_j$ 的高度超过了小红次能爬的高度 $P$ ， 那小红就不会选择这爬座山， 登山方案数为 $0$ 。