【题目描述】
小 G 是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是他每次看见地上的白道路和黑砖块就会犯强迫症。
在他的面前有一条大小为 $n\times m$ 的白色道路，他要用若干个 $1\times 2$ 的黑色砖块铺路。
他想知道有多少种留白的方式，使得砖块两两不交且完全在道路内。答案对 $P$ 取模。
【输入格式】
一行三个正整数 $n, m, P$，含义见题目描述。
【输出格式】
一行一个整数，表示你的答案。
【测试点约束】
本题采用捆绑测试。
对于所有测试点：$n\leq 5$，$m\leq 10^{18}$，$1 < P < 10^{9}+9$。
| 子任务编号 | $n= $ | $m\le$ | 分值 |
|---|---|---|---|
| $1$ | $1$ | $5$ | $1$ |
| $2$ | $1$ | $100$ | $3$ |
| $3$ | $1$ | $10^5$ | $5$ |
| $4$ | $1$ | $10^{18}$ | $7$ |
| $5$ | $2$ | $5$ | $1$ |
| $6$ | $2$ | $100$ | $3$ |
| $7$ | $2$ | $10^5$ | $5$ |
| $8$ | $2$ | $10^{18}$ | $7$ |
| $9$ | $3$ | $5$ | $1$ |
| $10$ | $3$ | $100$ | $3$ |
| $11$ | $3$ | $10^5$ | $5$ |
| $12$ | $3$ | $10^{18}$ | $7$ |
| $13$ | $4$ | $5$ | $1$ |
| $14$ | $4$ | $100$ | $3$ |
| $15$ | $4$ | $10^5$ | $7$ |
| $16$ | $4$ | $10^{18}$ | $15$ |
| $17$ | $5$ | $5$ | $1$ |
| $18$ | $5$ | $100$ | $3$ |
| $19$ | $5$ | $10^5$ | $7$ |
| $20$ | $5$ | $10^{18}$ | $15$ |