P405225 - GYM101848 I Chessboard - SSOJ - 省实信息奥赛评测系统

Memory Limit：512 MB Time Limit：5 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics MD

I. Chessboardtime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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 ≤ 10⁴, 2 ≤ p ≤ 10⁹, p is prime.)

Output

Output the answer modulo p.

ExamplesInput

2 2 998244353

Output

Input

4 3 998244353

Output

Input

3 3 998244353

Output

Note

Example 3 has the following 108 ways:

$\text{[math]}$

2018 ECNU Campus Invitational Contest

405225: GYM101848 I Chessboard

Description

Source/Category

加入题单