题目描述
我们称一个仅由 0,1 构成的序列为「交错序列」，当且仅当序列中没有相邻的 1（可以有相邻的 0）。例如，000,001,101 都是交错序列，而 110 则不是。

对于一个长度为 (n) 的交错序列，统计其中 0 和 1 出现的次数，分别记为 (x) 和 (y)。给定参数 (a,b)，定义一个交错序列的特征值为 (x^a y^b)。注意这里规定任何整数的 0 次幂都等于 1（包括 (0^0 = 1)）。

显然长度为 (n) 的交错序列可能有多个。我们想要知道，所有长度为 (n) 的交错序列的特征值的和，除以 (m) 的余数。（(m) 是一个给定的质数）

例如，全部长度为 3 的交错串为：000,001,010,100,101。当 (a=1,b=2) 时，可计算： [ 3^1\times 0^2 + 2^1\times 1^2 + 2^1\times 1^2 + 2^1\times 1^2 + 1^1\times 2^2 = 10。 ]

输入格式
共一行，包含三个空格分开的整数 (n,a,b) 和 (m)。

输出格式
共一行，为计算结果。

样例 1
输入：

3 1 2 1009

输出：

10

样例 2
输入：

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)。