Fresh Matrix

Time limit6sMemory limit256 MB

Summary

Count the n-by-m 0/1 matrices with no two side-adjacent 1s whose 0 cells form one connected region, modulo a prime p with m up to 1e9.

Level: Hard9 of 10
Topics: Dynamic programming, Matrix, Bit manipulation
Solved: No attempts yet

Problem

A matrix of 0s and 1s is good if no two 1s in cells that share a side. A matrix of 0s and 1s is connected if every pair of 0s is joined by a path that contains no 1s, where each pair of consecutive cells on the path shares a side.

How many good connected matrices of 0s and 1s with $n$ rows and $m$ columns are there? Print only the remainder modulo the prime $p$ .

Input

The first line contains three integers $n$ , $m$ , and $p$ : the number of rows, the number of columns, and the modulus. ( $2 \le n \le 11$ ; $1 \le m \le 10^9$ ; $2 \le p \le 10^9$ ; $p$ is prime.)

Output

Print one integer: the number of good connected matrices modulo $p$ .

Examples3

Example 1
Input
```
2 2 998244353
```
Expected output
```
5
```
Example 2
Input
```
4 1 998244353
```
Expected output
```
4
```
Example 3
Input
```
4 5 998244353
```
Expected output
```
2749
```