22131번 - Таблица 다국어

Рассмотрим прямоугольную таблицу, составленную из n×m клеток. Каждую клетку разрешается покрасить в черный либо в белый цвет. Раскраска называется правильной, если не существует четырех клеток одинакового цвета, центры которых расположены в углах невырожденного прямоугольника со сторонами, параллельными сторонам таблицы.

Требуется посчитать число различных правильных раскрасок прямоугольника. Так как это число может быть большим, необходимо вывести его по заданному модулю r.

Например, для прямоугольника 2×2 число таких раскрасок равно 14: подходят все раскраски, кроме тех, у которых все четыре клетки покрашены в один цвет.

В первой строке входного файла содержится натуральное число t — количество тестов (1 ≤ t ≤ 150).

В каждой из следующих t строк содержится 3 целых числа: n, m и r — размеры таблицы и модуль, по которому требуется вывести ответ. (1 ≤ n, m, r ≤ 10¹⁸)

Для каждого тестового запроса выведите ответ в отдельной строке.