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` ≤ 10^{9}), 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**
Submit
Status