题目描述

有一片 $H$ 行 $W$ 列的森林，每个格子中最初恰好有一棵树。行号向南增加，列号向东增加。每棵树上写着字母 S 或 E，分别表示“向南”和“向东”。

Limak 会按行优先顺序访问所有格子：先从左到右访问第一行，再访问第二行，以此类推。到达一个格子后执行：

1. 如果当前格子已经被一棵倒下的树占据，则什么也不做。
2. 否则，优先尝试把当前树推向树上字母表示的方向。如果可以推，就执行并结束当前格子的操作。
3. 若首选方向不可行，则尝试另一个方向；若可行就推倒。
4. 若两个方向都不可行，则不推树。

树只能向南或向东倒下。被推倒的树会同时占据原格子和相邻的目标格子；不能推到森林之外，也不能使两棵倒树占据同一格子。

每个格子的字母都可以独立取 S 或 E，因此一共有 $2^{WH}$ 种不同森林。对每一种森林执行上述过程，记 Limak 推倒的树数。求所有 $2^{WH}$ 种森林中推倒树数的总和，对给定质数 $MOD$ 取模。

输入格式

一行三个整数 $W,H,MOD$。

输出格式

输出所有森林中推倒树数量总和对 $MOD$ 取模的结果。

数据范围

$1\le W\le30$；$1\le H\le13$；$3\le MOD\le10^9$，且 $MOD$ 为质数。

样例

4 3 999999937

24064