Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
102 - ZOJ Monthly, January 2011 - B
A Simple Math Problem

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Give you two positive integers a and b, which satisfies 0 < b-a < 1+2sqrt(a), together with a positive even number n, please calculate the value of floor((sqrt(a)+sqrt(b))^n) % 2(a+b).

Input

There are multiple test cases. Each test case include three integers a, b and n (1 <= a <= 10000, 1 <= b <= 10000, 2 <= n <= 10^9).

Output

For each test case, output an single line contains the value of the formula described above.

Sample Input

21 29 1998

Sample Output

99

Author: JIANG, Kai
Contest: ZOJ Monthly, January 2011
Submit    Status