Xiao Chun has been feeling down lately. Facing $n$ cards on his desk, he decides to color each card. Currently, Xiao Chun only has $3$ colors: red ($r$), blue ($b$), and green ($g$). He asked Sun how many ways there are to color the cards, and Sun gave the answer quickly, which surprised Xiao Chun. Furthermore, Xiao Chun requested that $Sr$ cards be colored red, $Sb$ cards blue, and $Sg$ cards green, and he asked Sun how many coloring schemes exist for this; Sun thought for a moment and gave the correct answer again.

Finally, Xiao Chun invented $m$ different shuffling methods. He then asked Sun how many distinct coloring methods exist, where two coloring methods are considered the same if and only if one can be transformed into the other using any combination of the shuffling methods (i.e., multiple shuffling methods can be used, and each can be used multiple times). Sun found this problem a bit difficult, so he decided to hand it over to you. Since the answer might be very large, you are only required to output the remainder when the answer is divided by $p$ (where $p$ is a prime number).

Input

The first line contains 5 space-separated integers: $Sr$, $Sb$, $Sg$, $m$, and $p$, where $n=Sr+Sb+Sg$. The next $m$ lines each describe a shuffling method. Each line contains $n$ space-separated integers $x_1, x_2, \ldots, x_n$, which form a permutation of the integers from $1$ to $n$, indicating that after applying this shuffling method once, the card at position $i$ is the card that was originally at position $x_i$. The input data guarantees that any sequence of multiple shuffles can be represented by one of these $m$ shuffling methods, and for every shuffling method, there exists a shuffling method that can return the cards to the original state. Here, $m \le 60$, and $p$ is a prime number such that $m+1 < p < 100$.

20% of the input data satisfies: $n=Sr+Sb+Sg \le 20$.

100% of the input data satisfies: $\max\{Sr, Sb, Sg\} \le 20$.

Output

A single integer representing the total number of distinct coloring methods modulo $p$.

Examples

Input 1

1 1 1 2 7
2 3 1
3 1 2

Output 1

2

Note

There are 2 essentially distinct coloring methods: RGB and RBG. Using the shuffling method 2 3 1 once results in GBR and BGR, and using the shuffling method 3 1 2 once results in BRG and GRB.