Даны три целых числа x, m и n. Вычислите (1 + x + x^2
+ .. + x^m
) (mod n).
Первая строка содержит количество тестов. Каждая следующая строка содержит три целых числа x, m и n (1 ≤ x, m, n ≤ 10^16
).
Для каждого теста выведите ответ в отдельной строке.