Дано три цілих числа x, m и n. Обчисліть (1 + x + x2 + .. + xm) (mod n).

Вхідні дані

Перший рядок містить кількість тестів. Кожний наступний рядок містить три цілих числа x, m и n (1 ≤ x, m, n ≤ 1016).

Вихідні дані

Для кожного тесту виведіть відповідь в окремому рядку.