Description

There’re bacterias in the Petri dish. The only thing they can do is to reproduce themselves everyday.

After one bacteria reproduce itself, there will be one origin bacteria and y newborn bacterias.
Suppose there’re x bacterias on the first day.
Your task is to compute how many bacterias on the n-th day.

Please output the answer modulo 10177 because the answer may be too large to be represented by int.

Hint: if you got TLE, try to optimize power by recursion.

#define MOD 10177
// Ch7 Slide P.35
// compute an
int fast_pow(int a, int n){
    if( n == 0 ){ // basis
        return 1;
    }
    else{ // resursive 
        int k = ???;
        // if n is even:
        // return (k*k)%MOD
        // if n is odd:
        // return ???
    }
}

Input

There are multiple lines of input.
Each line contains 3 positive integers x,y,n

• 0 ≤ x, y ≤ 10,000
• 1 ≤ n ≤ 10,000,000
• The input is ended by EOF.

Output

Print the number of bacterias on the n-th day modulo 10177 for each line of input.
Remember ‘\n’ on the end of line.

Explantation of Sample I/O:

• (1, 0, 9): 1 bacteria at first day. There’re no newborn bacteria after reproduction. There’s still 1 bacteria on 9-th day.
• (4, 5, 6): 4 bacterias at first day. After every bacteria reproduce itself, there’re 4 + 4*5 bacterias on the second day. On 6-th day, there’re 31,104 bacterias, 31104 modulo 10177 = 573

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss