一只 Byteotian 蚂蚁正在 ABCDEFGH 立方体的棱上行走：

它想知道，从一个给定的顶点出发，沿着棱走恰好 $k$ 条边到达另一个给定的顶点，有多少种不同的走法（当蚂蚁进入一条边时，它不会中途折返，最终会到达这条边的另一端）。如果蚂蚁多次经过某条边 $x$ 次，我们将这条边计入 $x$ 次。蚂蚁希望走出的路线是“有趣的”，也就是说，当蚂蚁到达某个顶点时，它希望离开该顶点时所走的边，不能是刚才进入该顶点时所走的那条边（即它不想连续两次走同一条边）。

这只蚂蚁不太聪明，因为它只能用 $0$ 到 $p-1$ 之间的整数进行计数（对于某个 $p$），因此你需要计算结果对 $p$ 取模后的值。

请编写一个程序：

• 读取蚂蚁路线的起点和终点、路线包含的边数以及整数 $p$；
• 计算满足蚂蚁要求的“有趣”路线数量，并对 $p$ 取模；
• 将结果输出到标准输出。

输入格式

第一行包含两个大写英文字母 $v_{1}$ 和 $v_{2}$（$A \le v_{1}, v_{2} \le H$，$v_{1} \neq v_{2}$），中间用一个空格隔开。这两个字母分别表示蚂蚁路线的起点和终点。第二行包含两个整数 $k$ 和 $p$（$1 \le k \le 2\,000\,000\,000$，$2 \le p \le 1\,000\,000\,000$），中间用一个空格隔开。

输出格式

输出一个整数，表示从顶点 $v_{1}$ 到顶点 $v_{2}$ 且包含恰好 $k$ 条边的“有趣”路线数量，对 $p$ 取模。

样例

输入 1

A B
3 100

输出 1

2