Almost Video Game III

In Video Game II: Almost Video Game III, you control a character which has $K$ abilities, numbered from $0$ to $K-1$. The objective of this game is to defeat $N$ bosses, which are numbered from $0$ to $N-1$, in the order you have to beat them.

At the beginning of a playthrough, none of the $K$ abilities has been researched yet. Before facing each boss, you can research a (possibly empty) subset of the $K$ abilities. Once an ability is researched, it will stay available for the rest of the playthrough and you do not have to research it again.

After beating all bosses, the score of the playthrough is equal to $b^2$, where $b$ is the number of bosses where your character had all $K$ abilities researched.

Let’s consider the following playthrough for $N = 4$ and $K = 3$:

• Before fighting boss $0$, you research ability $2$.
• You fight boss $0$ with $1$ ability researched.
• Before fighting boss $1$, you don’t research any new abilities.
• You fight boss $1$ with $1$ ability (ability $2$) researched.
• Before fighting boss $2$, you research abilities $0$ and $1$.
• You fight boss $2$ with all $K = 3$ abilities researched.
• Before fighting boss $3$, you don’t research any new abilities.
• You fight boss $3$ with all $K = 3$ abilities researched.

Since you fought bosses $3$ and $4$ with all $K = 3$ abilities researched, $b$ is equal to $2$ and the score of this playthrough is $b^2 = 4$.

Task

What is the sum of the scores of all possible playthroughs? Two playthroughs are considered different if there exists a boss $i$ ($0 \le i < N$) that you fight having a different subset of abilities researched.

Since the answer can be large, print its remainder modulo $MOD$, where $MOD$ is a prime number given in the input.

Input data

The first line of input contains three integers $N$, $K$ and $MOD$: the number of bosses, the number of abilities, and the modulo.

Output data

Print one integer, the sum of the scores of all possible playthroughs modulo $MOD$.

Constraints and clarifications

• $1 \le N \le 10^{18}$
• $1 \leq K \leq 1 \ 000 \ 000$
• $10^8 \le MOD \le 10^9+7$ and $MOD$ is a prime number.

Example 1

stdin

3 2 100000007

stdout

26

Explanation

In this sample case, there are $N = 3$ bosses and $K = 2$ abilities.

A playthrough is denoted as a sequence of $N = 3$ sets $s_0 \subseteq s_1 \subseteq s_2$, where:

• $s_0 \subseteq \{0,1\}$ is the subset of the abilities researched before facing boss $0$;
• $s_1 \subseteq \{0,1\}$ is the subset of the abilities researched before facing boss $1$;
• $s_2 \subseteq \{0,1\}$ is the subset of the abilities researched before facing boss $2$.

In total, there are $16$ different playthroughs:

• $[\{\},\{\},\{\}]$, with a score of $0^2=0$.
• $[\{\},\{\},\{0\}]$, with a score of $0^2=0$.
• $[\{\},\{0\},\{0\}]$, with a score of $0^2=0$.
• $[\{0\},\{0\},\{0\}]$, with a score of $0^2=0$.
• $[\{\},\{\},\{1\}]$, with a score of $0^2=0$.
• $[\{\},\{1\},\{1\}]$, with a score of $0^2=0$.
• $[\{1\},\{1\},\{1\}]$, with a score of $0^2=0$.
• $[\{\},\{\},\{0,1\}]$, with a score of $1^2=1$.
• $[\{\},\{0\},\{0,1\}]$, with a score of $1^2=1$.
• $[\{0\},\{0\},\{0,1\}]$, with a score of $1^2=1$.
• $[\{\},\{1\},\{0,1\}]$, with a score of $1^2=1$.
• $[\{1\},\{1\},\{0,1\}]$, with a score of $1^2=1$.
• $[\{\},\{0,1\},\{0,1\}]$, with a score of $2^2=4$.
• $[\{0\},\{0,1\},\{0,1\}]$, with a score of $2^2=4$.
• $[\{1\},\{0,1\},\{0,1\}]$, with a score of $2^2=4$.
• $[\{0,1\},\{0,1\},\{0,1\}]$, with a score of $3^2=9$.

The sum of the scores across all possible playthroughs is $0 \cdot 7 + 1 \cdot 5 + 3 \cdot 4 + 9 = 0 + 5 + 12 + 9 = 26$.

Example 2

stdin

5 3 998244353

stdout

517

Example 3

stdin

999013 97 998244853

stdout

116848898

Example 4

stdin

958613246711292682 1000000 1000000007

stdout

112173097