#描述#
童鞋们已经对等差数列和Fibonacci数列非常了解了。
<BR>
所谓等差数列就是：
<BR>
g(i)=k*i+b;
<BR>
我们在这里假设k,b为非负整数。
<BR>
所谓Fibonacci数列就是：
<BR>
f(0)=0
<BR>
f(1)=1
<BR>
f(n)=f(n-1)+f(n-2) (n>=2)
<BR>
<BR>
现在小戴童鞋心中总有个问题无法解决：
<BR>
给你k,b,n，请你计算f(g(i)) 的和，其中i为[0,n),结果模取M。

#格式#
##输入格式##
数据存在多组，每组一行，有四个非负整数k,b,n,M。
每个数都不超过1,000,000,000。

##输出格式##
输出所要求得结果，每个结果占一行。

#样例1#
##样例输入1##

2 1 4 100
2 0 4 100

##样例输出1##

21
12

#限制#
5000ms
32768KB

#提示#

#来源#
guoxu