Ant

An ant walks along the edges of a cube $ABCDEFGH$.

The ant wants to find out in how many ways it can travel from one given vertex to another given vertex by crossing exactly $k$ edges. (Once the ant steps onto an edge it never turns back partway, and always walks all the way to the other end of that edge.) If the ant crosses some edge $x$ times, that edge is counted $x$ times.

The ant only wants to count interesting routes: whenever it arrives at a vertex, it wants to leave that vertex through an edge different from the one it just used to enter it (it never uses the same edge twice in a row).

The ant can only count integers from $0$ to $p - 1$ for some $p$, so report the answer modulo $p$.

The cube is structured as follows: the bottom face is the square $ABCD$ (edges $AB$, $BC$, $CD$, $DA$), the top face is the square $EFGH$ (edges $EF$, $FG$, $GH$, $HE$), and the vertical edges $AE$, $BF$, $CG$, $DH$ connect the two faces (12 edges in total).

Write a program that:

• reads the starting vertex, the ending vertex, the number of edges on the route, and the integer $p$,
• computes the number of interesting routes that satisfy the conditions above, modulo $p$,
• writes the answer to standard output.

The first line contains two uppercase English letters $v_1$ and $v_2$ ($A \le v_1, v_2 \le H$, $v_1 \ne v_2$), separated by a single space, denoting the starting and the ending vertex respectively. The second line contains two integers $k$ and $p$ ($1 \le k \le 2\,000\,000\,000$, $2 \le p \le 1\,000\,000\,000$), separated by a single space.

Output a single integer: the number of interesting routes from vertex $v_1$ to vertex $v_2$ using exactly $k$ edges, modulo $p$.