题目描述
我们称一个仅由 0,1 构成的序列为「交错序列」,当且仅当序列中没有相邻的 1(可以有相邻的 0)。例如,000,001,101 都是交错序列,而 110 则不是。
对于一个长度为 n 的交错序列,统计其中 0 和 1 出现的次数,分别记为 x 和 y。给定参数 a,b,定义一个交错序列的特征值为 xayb。注意这里规定任何整数的 0 次幂都等于 1(包括 00=1)。
显然长度为 n 的交错序列可能有多个。我们想要知道,所有长度为 n 的交错序列的特征值的和,除以 m 的余数。(m 是一个给定的质数)
例如,全部长度为 3 的交错串为:000,001,010,100,101。当 a=1,b=2 时,可计算:31×02+21×12+21×12+21×12+11×22=10。
输入格式
共一行,包含三个空格分开的整数 n,a,b 和 m。
输出格式
共一行,为计算结果。
样例 1
3 1 2 1009
10
4 3 2 1009
204
数据范围与提示
对于 30% 的数据,1≤n≤15。
对于 100% 的数据,1≤n≤107,0≤a,b≤45,m<108。