#### Registered Users Only

Please login to view and utilize this feature.

Ever done exponentiate? Yes? Good!

Now you need to calculate the hyperoperations!

You are given 4 numbers, T,A,B,M.
You are supposed to do the T'th operation on A, B times and output the remainder of the result divided by M.

- 1: successor
- 2: addition
- 3: multiplication
- 4: exponentiation

Of course, 4 is tetration. Have fun!

7^^4 = (7^(7^(7^7)));

X^^0 = 1 for all X

Constraints:

0 <= T,A,B,M <= 2^32-1

0 <= N <= 100000

Subtasks:

Subtask 1: T <= 1 (1%)

Subtask 2: T <= 2 (2%)

Subtask 3: T <= 3 (3%)

Subtask 4: T <= 4 (14%) If T is 4, 1<=A,B,M<=100

Subtask 5: T <= 4 (80%)

Input: First line: N, number of testcases

Subsequent N lines, 4 integers, T,A,B,M

Output: For each testcase, output the result

Sample Input:

6 1 1 2 10 2 2 2 10 3 3 3 4 4 3 2 20 4 3 3 345 4 993306745 75707320 1000000000Sample Output:

3 4 3 7 312 884765625

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 1 | 3 | 3s | 32MB | Minimum |

2 | 2 | 5 | 3s | 32MB | Minimum |

3 | 3 | 6 | 3s | 32MB | Minimum |

4 | 14 | 6 | 3s | 32MB | Minimum |

5 | 80 | 10 | 3s | 32MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o hyperoperations -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512