橙子并没能让汤圆冷静下来,现在只好让卷子出手了。
卷子将会发动 次魔法,每次都可以从 种魔法里选一种发动,每种魔法都可以发动无限次。
发动第 种魔法将会让汤圆的黑化值增加 。
为了稳定汤圆的情绪,卷子必须在任意时刻让汤圆的黑化值大于等于 并且小于等于 。
卷子想知道有多少种方案能够发动完这 次魔法。
第一行四个整数 ,,,表示卷子要发动 次魔法,一共有 种魔法可以选择,必须在任意时刻保证汤圆的黑化值大于等于 并且小于等于 ,数据保证 。
接下来输入 个整数 表示第 种魔法会让汤圆的黑化值增加
输出一行 行整数,第 行整数 表示汤圆的黑化值初始值为 时卷子能够稳定汤圆情绪的方案数。
由于方案数可能过大,请输出方案数 之后的结果。
5 5 40 45 -2 -1 0 1 2
874 1242 1539 1539 1242 874
具体来讲,一种方案可以看成一个长度为 的数列,若某种方案第 次选择发动第 种魔法,那么数列的第 项的值就是 (注意不是 ),只要两个数列中某一项不同则可以认为是两种不同的方案。
任意时刻包括初始时刻。