407504: GYM102803 H Hate That You Know Me

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Hate That You Know Metime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Little Y can't help himself learning number theory. However, math is too hard for him. He was beaten by SPOJ AFS3 and felt down. So here is a simple math problem.

Let $$$\sigma_k(n)$$$ be the following definition:

$$$$$$ \sigma_k(n) = \sum_{d|n} d^k $$$$$$

For example, when $$$k=0$$$, this function is known as the count of divisors of $$$n$$$. And when $$$k=1$$$, this function is known as the sum of divisors of $$$n$$$.

Now he wants to calculate the following fomula for given $$$a$$$ and $$$b$$$.

$$$$$$ \left( \left( \sum_{i=1}^n \sigma_a(i) \right) \oplus \left( \sum_{i=1}^n \sigma_b(i) \right) \right) \mod 2^{64} $$$$$$

where $$$\oplus$$$ means the bitwise exclusive or.

Input

One line containing three integer $$$a, b$$$ and $$$n$$$.

To be much simpler, it is guaranteed that $$$0 \leq a, b < 4$$$ and $$$1 \leq n \leq 10^{12}$$$. Then you can solve this problem without either interpolation or SPOJ DIVCNT1.

Output

One line containing the value.

ExamplesInput
0 1 4
Output
7
Input
2 3 2
Output
12

加入题单

上一题 下一题 算法标签: