Problem Description

B-Jun has two good friends named Ningning and Ranran. One day, Ranran came across an interesting problem: Given three non-negative integers \( b, d, n \), compute

\[ \left\lfloor \left ( \frac{b + \sqrt{d}}{2} \right )^n \right\rfloor \bmod p \]

where \( p = 7,528,443,412,579,576,937 \).

Input Format

A single line containing three non-negative integers \( b \), \( d \), and \( n \).

Output Format

A single line representing the result modulo \( 7,528,443,412,579,576,937 \).

Sample Input and Output

Sample Input #1

3 13 5

Sample Output #1

393

Sample Input #2

5 29 114514

Sample Output #2

4997196309027367968

Notes

It is guaranteed that \( 0 < b^2 \leq d < (b+1)^2 \leq 10^{18} \), \( n \leq 10^{18} \), and \( b \equiv 1 \pmod{2} \), \( d \equiv 1 \pmod{4} \).

见题面 Input 部分

见题面 Output 部分