题目描述

给定两个整数 $n$ 和 $m$，在所有包含 $n$ 个非负整数且每个整数都小于 $2^m$ 的序列中，你需要计算满足以下条件的序列 $A$ 的数量：存在一个 $A$ 的非空子序列，其中所有整数的按位与运算结果为 $1$。

注意，序列 $A$ 的非空子序列是指通过从 $A$ 中删除零个或多个元素（保持剩余元素的原始顺序）得到的非空序列。

由于答案可能非常大，请将其对一个正整数 $q$ 取模后输出。

非负整数 $A$ 和 $B$ 的按位与运算 $A\ \&\ B$ 定义如下：

• 当 $A\ \&\ B$ 以二进制表示时，$2^d$ 位（$d≥0$）的数字为 $1$ 当且仅当 $A$ 和 $B$ 在该位均为 $1$，否则为 $0$。

例如，$4\ \&\ 6 = 4$（二进制表示为 $100\ \&\ 110 = 100$）。

一般情况下，$k$ 个非负整数 $p_1,p_2,…,p_k$ 的按位与运算定义为 $(…((p_1\ \&\ p_2)\ \&\ p_3)\& … \&\ p_k)$，并且可以证明该值与 $p_1,p_2,…,p_k$ 的顺序无关。

输入格式

一行包含三个整数 $n$ $(1≤n≤5000)$、$m$ $(1≤m≤5000)$ 和 $q$ $(1≤q≤10^9)$。

输出格式

输出一行一个整数，表示答案。

2 3 998244353

17

5000 5000 998244353

2274146