Elizur 有一个空的 $n \times m$ 网格，他想使用一些 $1 \times 2$ 和 $2 \times 1$ 的多米诺骨牌来覆盖整个网格。在网格中，每个多米诺骨牌必须恰好覆盖两个相邻的方格，且每个方格必须恰好被一个多米诺骨牌覆盖。两个方格相邻当且仅当它们共用一条边。

显然，当且仅当 $n$ 和 $m$ 中至少有一个是偶数时，他才能做到这一点：否则，总会有一个方格无法被覆盖。因此，他想知道有多少种方法可以覆盖整个网格。如果两种覆盖方式中，存在两个多米诺骨牌（分别来自两种覆盖方式），使得它们覆盖的其中一个方格相同但另一个方格不同，则认为这两种方式是不同的。

你能帮他确定答案吗？答案可能非常大，所以他只要求你求出答案对一个质数 $p$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 20\,000$)，表示询问的数量。

接下来的 $T$ 行，每行包含三个整数 $n$ ($1 \le n \le 35$)，$m$ ($1 \le m \le 10^{18}$) 和 $p$ ($2 \le p \le 2^{30}$，$p$ 为质数)，描述一个询问。

保证满足 $n > 5$ 或 $m > 10^9$ 的测试用例不超过 $1000$ 个。

输出格式

对于每个询问，输出一行，包含一个整数，即答案对 $p$ 取模的结果。

样例

输入 1

6
2 2 23
2 3 233
3 3 2333
3 4 23333
4 4 2332333
5 251346744251346744 998244353

输出 1

2
3
0
11
36
295381485

说明

下图展示了 $3 \times 4$ 网格的所有可能覆盖方式（共 11 种）。