[CQOI2018] 交错序列

题目描述

我们称一个仅由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。

输出格式


输出文件共一行,为计算结果。

输入输出样例

输入样例 #1

3 1 2 1009

输出样例 #1

10

输入样例 #2

4 3 2 1009

输出样例 #2

204

说明

对于30%的数据,1≤n≤15 对于100%的数据,1≤n≤10000000 0≤a,b≤45 m<100000000