English Problem Statement

跳蚤王国的公敌“邪恶跳蚤大帅”设计了一种全新的高杀伤力地雷，并且多枚这种地雷被埋在了跳蚤王国的周围。

如果想彻底拆除地雷，就要输入正确的密码，已知所有地雷的密码均为长度为 $m$，元素均属于 $\{1, 2, \dots, n\}$ 的序列。

“邪恶跳蚤大帅”为了防止密码被破译，在设置完密码后就已经损毁了所有地雷的密码，而跳蚤技术所只复原出了密码的极少线索。对于每一个地雷的密码，设 $c_i$ 表示 $i$ 在密码中出现的次数，那么跳蚤技术所只成功复原出了所有 $c_{i-1}$ 和 $c_i$ 的大小关系，具体来说：

• 复原出的线索是一个长度为 $n-1$，所有元素均属于 $\{0, 1, 2\}$ 的线索序列 $t$，其中：
  • $t_i = 0$ 表示 $c_i < c_{i+1}$。
  • $t_i = 1$ 表示 $c_i = c_{i+1}$。
  • $t_i = 2$ 表示 $c_i > c_{i+1}$。

拿到跳蚤技术所破解的线索后，跳蚤王国的军事科技顾问“跳蚤福特黑客”仅用 $\text{0.01s}$ 就立刻破解了所有地雷的密码，跳蚤王国又恢复到了一片平静中。

这反常的速度立刻引起了你的怀疑，仅用如此少的信息根本不可能在如此快的时间内复原出所有地雷的密码，因此你怀疑“跳蚤福特黑客”和“邪恶跳蚤大帅”很可能是同一个人！

你决定立刻将此事上报给伏特跳蚤国王！但为了有足够的证据支撑，你需要计算出对于所有的线索序列 $t$，符合该线索的原密码有多少种，答案对质数 $p$ 取模。

输入格式

共一行，三个正整数 $n, m, p$。

输出格式

由于本题的输出量过大，采用压缩输出。

令 $f(t)$ 表示线索序列 $t$ 对应的原密码数模 $p$ 的余数，你只需要输出 $\bigoplus\limits_{t \in \{0, 1, 2\}^{n-1}} (h(t) \times (f(t) + h(t)))$ 即可，其中 $h(t) = \sum\limits_{i=1}^n 3^{i-1} t_i$。

2 4 998244353

9

样例解释

如下是输出压缩前，不同线索序列对应的原密码数：

• 当 $c_1 < c_2$ 时，$t = [0], f(t) = 5$。
• 当 $c_1 = c_2$ 时，$t = [1], f(t) = 6$。
• 当 $c_1 > c_2$ 时，$t = [2], f(t) = 5$。

3 10 1000000007

112586

样例解释

如下是输出压缩前，不同线索序列对应的原密码数：

• 当 $c_1 < c_2, c_2 < c_3$ 时，$t = [0, 0], f(t) = 5365$。
• 当 $c_1 = c_2, c_2 < c_3$ 时，$t = [1, 0], f(t) = 5551$。
• 当 $c_1 > c_2, c_2 < c_3$ 时，$t = [2, 0], f(t) = 14132$。
• 当 $c_1 < c_2, c_2 = c_3$ 时，$t = [0, 1], f(t) = 3402$。
• 当 $c_1 = c_2, c_2 = c_3$ 时，$t = [1, 1], f(t) = 0$。
• 当 $c_1 > c_2, c_2 = c_3$ 时，$t = [2, 1], f(t) = 5551$。
• 当 $c_1 < c_2, c_2 > c_3$ 时，$t = [0, 2], f(t) = 16281$。
• 当 $c_1 = c_2, c_2 > c_3$ 时，$t = [1, 2], f(t) = 3402$。
• 当 $c_1 > c_2, c_2 > c_3$ 时，$t = [2, 2], f(t) = 5365$。

5 100 998244353

67156055694

15 1000 1000000007

358612410956090

数据范围

对于所有数据，保证 $2 \leq n \leq 16, 1 \leq m \leq 1000, 0.99 \times 10^9 < p < 1.01 \times 10^9$，并且 $p$ 为质数。

时间限制：$5\texttt{s}$

空间限制：$2\texttt{GB}$

我们提供 $\text{Barrett}$ 模乘算法模板以加速取模运算：

#include<bits/stdc++.h>
using namespace std;
namespace FM{
typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod{
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {ull q = (ull)((L(m) * a) >> 64), r = a - q * b; return r >= b ? r - b : r;}
};
FastMod F(2);
}
unsigned int mod = 0;
struct modint{
unsigned int x;
modint() {x = 0;}
modint(int o) {x = o >= 0 ? o : mod - (-o);}
modint &operator = (int o) {return x = o, *this;}
modint &operator += (modint o) {return x = x + o.x >= mod ? x + o.x - mod : x + o.x, *this;}
modint &operator -= (modint o) {return x = x < o.x ? x - o.x + mod : x - o.x, *this;}
modint &operator *= (modint o) {return x = FM :: F.reduce(1ull * x * o.x), *this;}
modint &operator /= (modint o) {for(unsigned int t = mod - 2 ; t ; t >>= 1, o *= o) if(t & 1) *this *= o; return *this;}
friend modint operator + (modint a, modint b) {return a += b;}
friend modint operator - (modint a, modint b) {return a -= b;}
friend modint operator * (modint a, modint b) {return a *= b;}
friend modint operator / (modint a, modint b) {return a /= b;}
modint operator - () {return x ? mod - x : 0;}
};
void initmod(){
scanf("%u", &mod);
FM :: F = FM :: FastMod(mod);
}

</p>

请不要滥用本题评测（例如套数据等行为），滥用本题评测将被封号。