题目内容

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

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

塔子哥想知道，华光林的每座山各有多少种不同的爬山方案(输出结果对 $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$ 。