题目描述

薯条哥是一个热爱户外运动的人，他周末经常约朋友一起登山。华光林山清水秀，景色宜人，让他感到非常愉悦。

他喜欢在登山的过程中欣赏美景，感受大自然的魅力。同时，他也喜欢挑战自己，尝试攀登更高的山峰。

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

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

输入描述

第一行输入三个整数 $N,P,K(1\le N\le 10,1\le P,K\le 1000)$ 分别代表山的个数 $N$ ，薯条哥一次最高能爬的高度 $P$ 以及薯条哥一次最多能跨越的台阶数 $K$ 。

接下来 $N$ 行，每行的第一个整数 $M_i(1\le M_i\le 10^4)$ 表示第 $i$ 座山一共有 $M_i$ 个台阶，接下来有 $M_i$ 个整数，分别表示每个台阶的高度 $H_j(1\le H_j\le 1000)$

输出描述

输出 $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$ 。