Башня
Алан увлекается строительством башен из строительных кирпичей. Его башни состоят из прямоугольных параллелепипедов с квадратным основанием, причем все параллелепипеды имеют одинаковую высоту h = 1. Алан размещает параллелепипеды друг на друге:
Рисунок 1: Башня из трех кирпичей, когда Алан задает a_2 = 2.
Недавно на уроке математики Алан узнал о понятии объема. Теперь он хочет вычислить объем своей башни. Длины оснований параллелепипедов (сверху вниз) Алан определяет следующим образом:
Длина a_1 первого квадрата равна единице.
Затем Алан задает длину a_2 второго квадрата.
Далее Алан вычисляет длину a_n (n > 2) по формуле 2a_2a_{n-1} - a_{n-2}. Не спрашивайте, почему он выбрал такую формулу; просто скажем, что он действительно своеобразный молодой человек.
Например, если Алан задает a_2 = 2, то a_3 = 8 - a_1 = 7; см. Рисунок 1. Если Алан задает a_2 = 1, то a_n = 1 для всех n N; см. Рисунок 2.
Теперь Алан интересуется, может ли он вычислить объем башни из N последовательных строительных кирпичей. Помогите Алану, написав программу, которая вычисляет этот объем. Поскольку он может быть довольно большим, достаточно вычислить ответ по модулю данного натурального числа m.
Входные данные
Вход содержит несколько тестов. Первая строка содержит число t (t ≤ 10^5), обозначающее количество тестов. Далее следуют t тестов. Каждый из них дан в отдельной строке, содержащей три целых числа a_2, N, m (1 ≤ a_2, m ≤ 10^9, 2 ≤ N ≤ 10^9), разделенных одним пробелом, где a_2 обозначает фиксированную длину второго квадрата на шаге 2, а N обозначает количество кирпичей, построенных Аланом.
Выходные данные
Для каждого теста (a_2, N, m) вычислите объем башни из N последовательных кирпичей, построенных Аланом в соответствии с шагами (1-3), и выведите его остаток по модулю m.
Рисунок 2: Башня из четырех кирпичей, когда Алан задает a_2 = 1.