在课堂上，沃老师布置了一道难题。
初始有一个数字 , 你有 次操作机会且必须操作 次， 可以选择两种操作：
操作 ： 令 .
除此之外，数字 需要每时每刻满足 ，沃老师的问题是：有多少种操作序列满足条件？
睡了一节课的 Starry 同学被沃老师点到名回到这个问题，你能帮他算出答案吗？
操作序列的定义：由操作数按顺序组成的排列，例如当 时，将 变为 的一个操作序列为 ()。
两个操作序列存在某一项不同时则被认为是不同的，由于答案可能很大，你只需要输出答案对 取模的值。
一行四个由空格隔开的整数 ，
输出一行一个整数表示答案
3 1 -1 1
4
10 2 -10 3
396
对于样例一, 满足条件的操作序列有：