I. Chessboard
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Count how many ways there are to color a m × n chessboard with black and white, such that the black blocks are 4-connected, and the white blocks are also 4-connected.

Input

Three space-separated integers n, m, p. (1 ≤ m ≤ 8, 1 ≤ n·m ≤ 104, 2 ≤ p ≤ 109, p is prime.)

Output

Output the answer modulo p.

Examples
Input
2 2 998244353
Output
14
Input
4 3 998244353
Output
294
Input
3 3 998244353
Output
108
Note

Example 3 has the following 108 ways: