Вежа#5735

Вежа

1 секунда

64 мегабайти

Дуже складна

Алан любить будувати вежі з будівельних цеглин. Його вежі складаються з прямокутних паралелепіпедів з квадратною основою, причому всі вони мають однакову висоту $h = 1$ h = 1. Алан розміщує ці паралелепіпеди один на одному:

Рисунок 1: Вежа з трьох цеглин, коли Алан обирає $a_{2} = 2$ a_2 = 2.

Нещодавно на уроці математики Алан дізнався про об'єм, і тепер він хоче обчислити об'єм своєї вежі. Довжини основ паралелепіпедів (зверху вниз) Алан визначає так:

Довжина $a_{1}$ a_1 першого квадрата дорівнює одиниці.
Потім Алан обирає довжину $a_{2}$ a_2 другого квадрата.
Далі Алан обчислює довжину $a_{n}$ a_n ( $n > 2$ n > 2) за формулою $2 a_{2} a_{n - 1} - a_{n - 2}$ 2a_2 a_{n-1} - a_{n-2}. Не питайте, чому він обрав таку формулу; просто скажімо, що він дуже своєрідний молодий хлопець.

Наприклад, якщо Алан обирає $a_{2} = 2$ a_2 = 2, то $a_{3} = 8 - a_{1} = 7$ a_3 = 8 - a_1 = 7; див. Рисунок 1. Якщо Алан обирає $a_{2} = 1$ a_2 = 1, то $a_{n} = 1$ a_n = 1 для всіх $n \in N$ n \in \mathbb{N}; див. Рисунок 2.

Тепер Алан цікавиться, чи може він обчислити об'єм вежі з $N$ послідовних будівельних цеглин. Допоможіть Алану і напишіть програму, яка обчислює цей об'єм. Оскільки він може бути досить великим, достатньо обчислити відповідь за модулем заданого натурального числа $m$ .

Вхідні дані

Вхід містить кілька тестових випадків. Перша строка містить число $t$ ( $t \leq 1 0^{5}$ t \le 10^5), що позначає кількість тестових випадків. Потім слідують $t$ тестових випадків. Кожен з них подається в окремій строкі, що містить три цілі числа $a_{2}$ a_2, $N$ , $m$ ( $1 \leq a_{2}, m \leq 1 0^{9}$ 1 \le a_2, m \le 10^9, $2 \leq N \leq 1 0^{9}$ 2 \le N \le 10^9), розділені одним пробілом, де $a_{2}$ a_2 позначає фіксовану довжину другого квадрата на кроці $2$ , а $N$ позначає кількість цеглин, побудованих Аланом.

Вихідні дані

Для кожного тестового випадку ( $a_{2}$ a_2, $N$ , $m$ ) обчисліть об'єм вежі з $N$ послідовних цеглин, побудованих Аланом відповідно до кроків ( $1$ - $3$ ), і виведіть його залишок за модулем $m$ .

Рисунок 2: Вежа з чотирьох цеглин, коли Алан обирає $a_{2} = 1$ a_2 = 1.

Приклади

Приклад 1