Description

童鞋们已经对等差数列和Fibonacci数列非常了解了。

所谓等差数列就是：

g(i)=k*i+b;

我们在这里假设k,b为非负整数。

所谓Fibonacci数列就是：

f(0)=0

f(1)=1

f(n)=f(n-1)+f(n-2) (n>=2)

现在小戴童鞋心中总有个问题无法解决：

给你k,b,n，请你计算f(g(i)) 的和，其中i为[0,n),结果模取M。

Input

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

Output

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

Sample

Input

2 1 4 100
2 0 4 100

Output

21
12

Source: guoxu