Дано три цілих числа x, m и n. Обчисліть (1 + x + x^2
+ .. + x^m
) (mod n).
Перший рядок містить кількість тестів. Кожний наступний рядок містить три цілих числа x, m и n (1 ≤ x, m, n ≤ 10^16
).
Для кожного тесту виведіть відповідь в окремому рядку.