塔子哥是一个热爱户外运动的人,他周末经常约朋友一起登山。华光林山清水秀,景色宜人,让他感到非常愉悦。他喜欢在登山的过程中欣赏美景,感受大自然的魅力。同时,他也喜欢挑战自己,尝试攀登更高的山峰。
塔子哥登山时每一步可以选择向上爬一个台阶或者多个台阶,如果登山时选择的台阶不同,则为一种爬山方案。
塔子哥想知道,华光林的每座山各有多少种不同的爬山方案(输出结果对 109+7 取模)。
第一行,三个整数 N 、 P 和 K 分别代表山的个数 N ,塔子哥一次最高能爬的高度 P 以及塔子哥一次最多能跨越的台阶数 K 。
( 1≤N≤10 , 1≤P≤1,000 , 1≤K≤1,000 )
接下来 N 行,每行的第一个整数 Mi 表示第 i 座山一共有 Mi 个台阶,接下来有 Mi 个整数,分别表示每个台阶的高度 Hj
( 1≤Mi≤10,000,1≤Hj≤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
如果某一台阶 Hj 的高度超过了塔子哥次能爬的高度 P , 那塔子哥就不会选择这爬座山, 登山方案数为 0 。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.