其实也不是太模板。

题目描述

某人开发了一个消消乐游戏。

这个游戏的初始局面是一个$n\times m$的矩阵，每个位置有一只小动物，编号为$1,...,k$之一。

显然，这个局面有$k^{nm}$种之多。

如果一行或者一列中相邻的三个小动物是一样的，就会被消掉，那么游戏一开始难度就太低了。

问：有多少种初始局面满足任意三个相邻的小动物都不全一样。输出答案$mod \ P$。

输入格式

多组数据，请使用$while (cin>>n>>m>>k>>P)$来读入。

最多$40$组数据。

$n=m=6,k\leq 4,P\leq 1e9+7$。

输出格式

对于每一个输入，输出一个答案。

样例 #1

样例输入 #1

1 1 1 998244353
2 2 3 998244353
1 3 1 998244353
3 3 3 998244353

样例输出 #1

1
81
0
9750

提示

请使用按格点转移的方式来写，主要是帮你练练按格点转移。

此外不要打表。