Every HAYJlloween, Sean sets up a \(R\) by \(C\) grid of cells and forcibly imprisons Raymond's ghost on cell \((1, 1)\). Raymond's ghost is strange in that it must make \(K\) turns and can only move along the positive cardinal directions, lest it implode. To help Raymond's ghost escape, compute the number of ways for Raymond's ghost to go from cell \((1, 1)\) to cell \((R, C)\) while making exactly \(K\) turns, modulo \(M\).

Note: Two ways of travelling from \((1, 1)\) to \((R, C)\) are considered different if they go through a different set of cells. A turn is defined as leaving a cell in a different direction compared to how you entered the cell.

Constraints

\(1 \leq M \leq 10^{9}\)

Subtask 1 [30%]

\(1 \leq R, C \leq 4\)

\(0 \leq K \leq 8\)

Subtask 2 [70%]

\(1 \leq R, C \leq 10^{2}\)

\(0 \leq K \leq 2 \times 10^{2}\)

Input Specification

The first and only line contains four integers, \(R, C, K\), and \(M\).

Output Specification

Output one integer, the number of ways for Raymond's ghost to travel through the grid.

Sample Input

2 2 1 100

Sample Output

2