A Simple Sum#8655
Sign in

A Simple Sum

1 second
128 megabytes
Medium

Three integers , and are given. Compute the value of the following expression:

(1 + x + x^2 + \dots + x^m) \bmod p.

Input

The first line contains the number of test cases . Each of the following lines contains three integers x~(1 \le x \le 10^9), m~(1 \le m \le 10^{12}) and p~(1 \le p \le 10^9). It is guaranteed that is a prime number.

Output

For each test case, print the answer on a separate line.

Examples

Example 1

Loading
Loading