탑

앨런은 정육면체 모양 벽돌을 쌓아 탑 만드는 것을 좋아한다. 탑은 정사각형 밑면을 가진 여러 개의 직육면체로 이루어지며, 모든 직육면체의 높이는 $h = 1$로 같다. 앨런은 직육면체를 하나씩 위로 쌓아 올린다.

그림 1: 앨런이 $a_2 = 2$로 정했을 때 벽돌 3개로 이루어진 탑.

최근 수학 시간에 부피의 개념을 배운 앨런은 자신이 만든 탑의 부피를 구하고 싶어졌다. 위에서 아래로 내려가며 각 직육면체 밑면의 한 변의 길이는 다음 규칙으로 정해진다.

1. 첫 번째 정사각형의 변의 길이 $a_1$은 $1$이다.
2. 두 번째 정사각형의 변의 길이 $a_2$는 앨런이 직접 정한다.
3. $n > 2$인 경우, 길이 $a_n$은 $a_n = 2 a_2 a_{n-1} - a_{n-2}$로 계산한다. 왜 이런 식을 골랐는지는 묻지 말자. 그는 그저 별난 친구일 뿐이다.

예를 들어 앨런이 $a_2 = 2$로 정하면 $a_3 = 8 - a_1 = 7$이다(그림 1 참고). 앨런이 $a_2 = 1$로 정하면 모든 $n \in \mathbb{N}$에 대해 $a_n = 1$이 성립한다(그림 2 참고).

그림 2: 앨런이 $a_2 = 1$로 정했을 때 벽돌 4개로 이루어진 탑.

이제 앨런은 연속한 $N$개의 벽돌로 이루어진 탑의 부피를 계산하고 싶다. 각 직육면체의 부피는 (밑면의 넓이) $\times$ (높이) $= a_n^2$이므로, 탑 전체의 부피는 $\sum_{n=1}^{N} a_n^2$이다. 이 값은 매우 커질 수 있으므로, 주어진 자연수 $m$으로 나눈 나머지를 구하면 된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에는 테스트 케이스의 개수 $t$ ($t \le 10^5$)가 주어진다. 이어서 $t$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄에 공백 하나로 구분된 세 정수 $a_2$, $N$, $m$ ($1 \le a_2, m \le 10^9$, $2 \le N \le 10^9$)으로 주어진다. 여기서 $a_2$는 2단계에서 앨런이 정한 두 번째 정사각형의 변의 길이이고, $N$은 앨런이 쌓은 벽돌의 개수이다.

각 테스트 케이스 $(a_2, N, m)$에 대해, 규칙 (1)–(3)에 따라 쌓은 $N$개의 벽돌로 이루어진 탑의 부피 $\sum_{n=1}^{N} a_n^2$을 $m$으로 나눈 나머지를 한 줄에 하나씩 출력한다.