题目描述

Given two integers $n$ and $m$, among all the sequences containing $n$ non-negative integers less than $2^m$, you need to count the number of such sequences $A$ that there exists a non-empty subsequence of $A$ in which the bitwise AND of the integers is $1$.

Note that a non-empty subsequence of a sequence $A$ is a non-empty sequence that can be obtained by deleting zero or more elements from $A$ and arranging the remaining elements in their original order.

Since the answer may be very large, output it modulo a positive integer $q$.

The bitwise AND of non-negative integers $A$ and $B$, $A\ \&\ B$ is defined as follows:

• When $A\ \&\ B$ is written in base two, the digit in the $2^d$'s place ($d≥0$) is $1$ if those of $A$ and $B$ are both $1$, and $0$ otherwise.

For example, we have $4\ \&\ 6$ = $4$ (in base two: $100\ \&\ 110$ = $100$).

Generally, the bitwise AND of $k$ non-negative integers $p_1,p_2,…,p_k$ is defined as $(…((p_1\ \&\ p_2)\ \&\ p_3)\& … \&\ p_k)$ and we can prove that this value does not depend on the order of $p_1,p_2,…,p_k$.

输入格式

The only line contains three integers $n$ $(1≤n≤5000)$, $m$ $(1≤m≤5000)$ and $q$ $(1≤q≤10^9)$.

输出格式

Output a line containing an integer, denoting the answer.

2 3 998244353

17

5000 5000 998244353

2274146