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