Tower

Alan loves to build towers out of building bricks. His towers consist of many cuboids with a square base. All cuboids have the same height $h = 1$. Alan stacks the cuboids one on top of another.

Figure 1: A tower of three bricks when Alan fixes $a_2 = 2$.

Recently, in math class, Alan learned about the concept of volume, so now he wants to compute the volume of his tower. Going from top to bottom, the side length of each cuboid's square base is defined as follows.

1. The side length $a_1$ of the first square is $1$.
2. Alan fixes the side length $a_2$ of the second square himself.
3. For $n > 2$, the side length $a_n$ is computed as $a_n = 2 a_2 a_{n-1} - a_{n-2}$. Do not ask why he chose this formula; let us just say he is a truly peculiar young fellow.

For example, if Alan fixes $a_2 = 2$, then $a_3 = 8 - a_1 = 7$ (see Figure 1). If Alan fixes $a_2 = 1$, then $a_n = 1$ holds for every $n \in \mathbb{N}$ (see Figure 2).

Figure 2: A tower of four bricks when Alan fixes $a_2 = 1$.

Now Alan wonders whether he can compute the volume of a tower made of $N$ consecutive bricks. Since each cuboid's volume is (base area) $\times$ (height) $= a_n^2$, the volume of the whole tower is $\sum_{n=1}^{N} a_n^2$. Because this value can be quite large, it is enough to output the answer modulo a given natural number $m$.

The input contains several test cases. The first line contains the number $t$ ($t \le 10^5$) of test cases. Then $t$ test cases follow. Each test case is given on a single line containing three integers $a_2$, $N$, $m$ ($1 \le a_2, m \le 10^9$, $2 \le N \le 10^9$) separated by a single space, where $a_2$ is the fixed side length of the second square from step 2 and $N$ is the number of bricks Alan builds.

For each test case $(a_2, N, m)$, output on its own line the volume $\sum_{n=1}^{N} a_n^2$ of the tower of $N$ consecutive bricks built according to rules (1)–(3), taken modulo $m$.