Counting Magical Grid Journeys

Consider an n × m grid with its top‐left cell labeled \((1,1)\) and bottom‐right cell labeled \((n,m)\). Some cells are forbidden. There are s forbidden cells, each given by its coordinates; Dora (哆来咪) cannot step into these cells.

Dora starts at \((1,1)\) and wants to travel to \((n,m)\). In each step she can move one cell to the right or one cell down, provided she does not leave the grid and does not enter a forbidden cell. In addition, Dora has k magic potions. At any point (except when she is at \((1,1)\)) she may use a potion. Using a potion undoes the effect of her most recent movement that has not yet been undone and is a normal forward move (i.e. a move to the right or a move down). The potion “cancels” that forward move by making an extra move in the opposite direction: if the last forward move was to the right, the potion moves her left; if it was down, the potion moves her up. Note that the movement record (the sequence of moves) still keeps all moves – even the ones later undone – and potions do not cancel another potion’s move.

For example:

• If Dora goes from \(A\) to \(B\) and then uses a potion, her record becomes \(A \to B \to A\).
• If she goes \(A \to B \to C\) and then drinks two potions consecutively, her record becomes \(A \to B \to C \to B \to A\).

A journey is defined as any route that finally reaches \((n,m)\). Two journeys are considered different if and only if their complete movement records (the ordered list of moves) are different. Your task is to compute the number of essentially different journeys Dora can take modulo \(p\). The moves Dora can take are:

• Forward moves: either right (\(R\)) or down (\(D\)).
• Potion moves: if available and allowed, these moves are forced reversals of the last forward move (\(R\) becomes left \(L\) and \(D\) becomes up \(U\)).

Note:

• At the starting cell \((1,1)\) a potion cannot be used.
• A potion only cancels a forward move; it never cancels the effect of a previous potion move.
• Every move (forward or potion) must keep Dora inside the \(n\times m\) grid and she cannot step into a forbidden cell.

Given the grid dimensions \(n\) and \(m\), the number of forbidden cells \(s\) along with their coordinates, the number of potions \(k\), and the modulus \(p\), compute the number of different journeys Dora can make modulo \(p\).

inputFormat

The first line of input contains five integers: \(n\), \(m\), \(s\), \(k\), and \(p\) (\(1 \le n, m \le 10\), \(0 \le s \le n\times m-2\), \(0 \le k \le 10\)). It is guaranteed that neither \((1,1)\) nor \((n,m)\) is forbidden.

Then follow \(s\) lines; each contains two integers \(x\) and \(y\) indicating that cell \((x,y)\) is forbidden.

outputFormat

Output a single integer: the number of different journeys modulo \(p\).

sample

2 2 0 1 100

6