Medium

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

Given three integers x, m and n. Evaluate (1 + x + `x^2`

+ .. + `x^m`

) (mod n).

First line contains the number of test cases. Each next line contains three space separated integers x, m and n (1 ≤ x, m, n ≤ `10^16`

).

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

Input #1

Answer #1