Welcome to ZOJ
Select Problem
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 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.


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

Sample Input

2 2
1 1 1

Sample Output


Author: LIN, Xi
Source: ZOJ Monthly, February 2016
Submit    Status