# Ginomial Theorem

Time Limit: 2 Seconds

Memory Limit: 65536 KB

## Description

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

None