e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Exponentiation

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 (1x, m, n1016).

Output

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

Time limit 1 second
Memory limit 128 MiB
Input example #1
1
3 2 5
Output example #1
3