Даны три целых числа x, m и n. Вычислите (1 + x + x2 + .. + xm) (mod n).

Входные данные

Первая строка содержит количество тестов. Каждая следующая строка содержит три целых числа x, m и n (1 ≤ x, m, n ≤ 1016).

Выходные данные

Для каждого теста выведите ответ в отдельной строке.