#2533. 「CQOI2018」交错序列

内存限制:512 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

我们称一个仅由 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\leq n\leq 15

对于 100\% 的数据, 1\leq n\leq 10^7,0\leq a,b\leq 45, m<10^8