We all know what Binomial Theorem is:
(X+Y)N=∑i=0N(Ni)XN−i Yi
If we replaces i with (i, N), where (i,N) denotes the greatest common divisor of i and N, then we will get another theorem called Ginomial Theorem:
[X+Y]N=∑i=0N(N(i,N))XN−(i,N) Y(i,N)
And to make it simple, let's call it G(X, Y, N).
Now there's a problem with Ginomial Theorem for you:
Let F(N) be the Fibonacci sequence:
F(N)={NF(N−1)+F(N−2) N∈{0,1} N≥2
Please output F(G(X, Y, N)) mod 961749331
However, something unexpected happened. The real G(X, Y, N) you see is not what described above. What you see and you should use is below:
G(X,Y,N)=∑i=0N(N(i,N))XN−(i,N) Yi
Unfortunately, you need to use the wrong G(X, Y, N) to calculate F(G(X, Y, N)) mod 961749331.
Input
Input will consist of multiple test cases. Each case contains one line with three integers X, Y, N (1 ≤ X, Y, N ≤ 109), separated by spaces.
Output
One line for each case, you should output F(G(X, Y, N)) mod 961749331.
Sample Input
1 1 3
1 1 4
1 1 5
2 1 3
2 3 5
Sample Output
21
987
17711
121393
5183380
Hint
G(1, 1, 3) = 1 + 3 + 3 + 1 = 8, F(8) = 21
G(1, 1, 4) = 1 + 4 + 6 + 4 + 1 = 16, F(16) = 987