Problems
A Simple Sum
A Simple Sum
Given three integers x, m and n. Evaluate (1 + x + x2
+ .. + xm
) (mod n).
Input
First line contains the number of test cases. Each next line contains three space separated integers x, m and n (1 ≤ x, m, n ≤ 1016
).
Output
For each test case print the answer on a separate line.
Input example #1
1 3 2 5
Output example #1
3