我们称一个仅由 0,1 构成的序列为「交错序列」，当且仅当序列中没有相邻的 1 （可以有相邻的 0 ）。例如， 000,001,101 都是交错序列，而 110 则不是。
对于一个长度为 n 的交错序列，统计其中 0 和 1 出现的次数，分别记为 x 和 y 。给定参数 a,b ，定义一个交错序列的特征值为 x^ay^b 。注意这里规定任何整数的 0 次幂都等于 1 （包括 0^0=1 ）。
显然长度为 n 的交错序列可能有多个。我们想要知道，所有长度为 n 的交错序列的特征值的和，除以 m 的余数。（ m 是一个给定的质数）
例如，全部长度为 3 的交错串为： 000,001,010,100,101 。当 a=1,b=2 时，可计算： 3^1\times0^2+2^1\times1^2+2^1\times1^2+2^1\times1^2+1^1\times2^2=10 。
共一行，包含三个空格分开的整数 n,a,b 和 m 。
共一行，为计算结果。
3 1 2 1009
10
4 3 2 1009
204
对于 30\% 的数据， 1\leq n\leq 15 。
对于 100\% 的数据， 1\leq n\leq 10^7,0\leq a,b\leq 45, m<10^8 。