Sigma Function

Time Limit: 10 Seconds
Memory Limit: 65536 KB

The divisor function `σ`_{k}(n) for `n` an integer is defined as the sum of the `k`-th powers of the (positive integer) divisors of `n`.

And `f(n, m, k)` is defined as the following:

where `gcd(a, b)` is the greatest common divisor of `a` and `b`.

You are given four integers `N`, `M`, `X`, `C`. Please calculate the value of gao3(`N`, `M`, `X`) mod `C`.

#### Input

Input will consist of multiple test cases.

The first line contains two integers `N` and `M` (1 ≤ `N`, `M` ≤ 10^{7}).

The second line contains three integers `a`, `b`, `c` (1 ≤ `a`, `b`, `c` ≤ 10^{9}) indicating the value of `X` (eg. `X` = `a`^{b} + `c`).

The third line contains an integer `C` (1 ≤ `C` ≤ 10^{18}).

**Let **`C` = `p`_{1}^{a1}`p`_{2}^{a2}···`p`_{k}^{ak}, where `p`_{i} are distinct primes and `a`_{i} ≥ 1. It's guaranteed that 1 ≤ `a`_{i} < `p`_{i} ≤ 100 and `k` ≤ 5 and `p`_{i}^{ai} ≤ 10^{9}.

#### Output

One line for each case, you should output gao3(`N`, `M`, `X`) mod `C`.

#### Sample Input

2 2
1 1 1
3

#### Sample Output

2

Author:

**LIN, Xi**
Source:

**ZOJ Monthly, February 2016**
Submit
Status