Alan 喜欢用积木搭建塔。他的塔由许多底面为正方形的长方体组成。所有长方体的高度均为 $h = 1$。Alan 将这些长方体一个接一个地叠放在一起：

图 1：当 Alan 确定 $a_2 = 2$ 时，由三块积木组成的塔。

最近在数学课上，Alan 学习了体积的概念。因此，他现在想计算他的塔的体积。Alan 按以下方式确定长方体底面（从上到下）的边长：

• 1. 第一层正方形的边长 $a_1$ 为 $1$。
• 1. 接着，Alan 确定第二层正方形的边长 $a_2$。
• 1. 随后，Alan 通过公式 $a_n = 2 a_2 a_{n-1} - a_{n-2}$ 计算第 $n$ 层（$n > 2$）的边长 $a_n$。不要问他为什么选择这样一个公式，我们只能说他是一个非常古怪的小伙子。

例如，如果 Alan 确定 $a_2 = 2$，那么 $a_3 = 8 - a_1 = 7$；参见图 1。如果 Alan 确定 $a_2 = 1$，那么对于所有 $n \in \mathbb{N}$，都有 $a_n = 1$；参见图 2。

现在 Alan 想知道他是否能计算出由 $N$ 块积木组成的塔的体积。请帮助 Alan 编写一个程序来计算这个体积。由于体积可能非常大，只需计算答案模给定自然数 $m$ 的余数即可。

图 2：当 Alan 确定 $a_2 = 1$ 时，由四块积木组成的塔。

输入格式

输入包含多组测试数据。第一行包含一个整数 $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$ 表示 Alan 搭建的积木数量。

输出格式

对于每组测试数据 ($a_2, N, m$)，计算 Alan 根据步骤 (1–3) 搭建的由 $N$ 块积木组成的塔的体积，并输出其模 $m$ 的余数。

样例

输入样例 1

3
2 3 100
1 4 1000
3 3 1000000000

输出样例 1

54
4
299