#P18413. Courses
Courses
Courses
标准输入、标准输出。
小 Misha 想改变自己的 IQ。他最初的 IQ 为 。他在网上找到了 类课程:第 类课程的每门课程花费 个比特币,使 IQ 改变 ( 可以为负,也就是 IQ 可能降低),这一类共有 门不同的课程。课程作者希望赚钱,因此 。
Misha 想让最终 IQ 至少为 ,其中 也可以为负。为此,他每天学习一门课程,并在某一天结束学习。**同一门课程可以重复学习,每次都会使 IQ 发生相应变化。**IQ 允许为负,达标条件在学习结束时检查。
现在他有 个比特币。请对每个 ,求他恰好花费 个比特币、结束时 IQ 至少为 的学习方案数。
若两种方案的学习天数不同,或某一天所选的具体课程不同,就认为它们不同;同一类中的不同课程也算不同的选择。
输入格式
第一行一个整数 (),表示课程类型数量。
接下来 行,每行三个整数 ,满足
$$0<c_i<10,\qquad |d_i|\le c_i,\qquad 0\le n_i\le10^4.$$最后一行两个整数 ,满足 且 。
输出格式
输出 个整数,每行一个。第 行表示恰好花费 个比特币且最终 IQ 至少为 的方案数,对 取模。
样例 1
1
1 1 2
5 2
0
4
8
16
32
样例 2
2
1 -1 1
1 1 2
4 2
0
4
8
48