Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3848
Ginomial Theorem

Time Limit: 2 Seconds      Memory Limit: 65536 KB

We all know what Binomial Theorem is:

$$(X+Y)^{N}= \sum_{i=0}^{N}{N \choose i}X^{N-i}~Y^{i}$$

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 = \sum_{i=0}^{N}{N \choose (i,N)}X^{N-(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) = \begin{cases} N & {~~ N \in \{0,1\} } \\ F(N-1)+F(N-2) & {~~ N \geq 2} \end{cases}$$

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) = \sum_{i=0}^{N}{N \choose (i,N)}X^{N-(i,N)} ~ Y^{i}$$

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
Author: LIN, Xi
Source: ZOJ Monthly, January 2015
Submit    Status