Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3920
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 ≤ 107).
The second line contains three integers a, b, c (1 ≤ a, b, c ≤ 109) indicating the value of X (eg. X = ab + c).
The third line contains an integer C (1 ≤ C ≤ 1018).

Let C = p1a1p2a2···pkak, where pi are distinct primes and ai ≥ 1. It's guaranteed that 1 ≤ ai < pi ≤ 100 and k ≤ 5 and piai ≤ 109.

#### 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