---
# System prepended metadata

title: Grassfapper

---

# Grassfapper

> By Tzaph fan club

Joshjms is a professional CP-er, where CP does not stand for competitive programming. In his daily routine, Joshjms likes to fap for a total of $F$ times. Of course, one does not simply fap with no trigger material. Being a candidate master in a site appropriately abbreviated as CF, Joshjms has $(G+H)$ fapping materials consisting of $G$ types of grass (numbered $g_1$ to $g_G$) and $H$ types of two-dimensional erotic art (numbered $h_1$ to $h_H$). Each type of grass has an $N$-character code made up of uppercase Latin alphabets `A` to `Z`, while each type of two-dimensional erotic art (hereafter referred to as 2DEA) has an $N$-digit code of digits `0` to `9`.

Joshjms, with years of experience, has formulated a sequence of picking fapping materials that maximizes the pleasure that he receives. The sequence goes as follows:

- Joshjms always starts at either grass $g_S$ or 2DEA $h_S$.
- If Joshjms is currently using grass $g_i$, he could either use $h_i$ next (if available) or choose another grass $g_j$ such that there are at least two different letters which appear in both $g_i$ and $g_j$'s code.
- If Joshjms is currently using 2DEA $h_i$, he could either use $g_{2i}$ next (if available) or choose another 2DEA $h_j$ which satisfies $\left(h_i^{h_j}\right) \; \text{mod} \; m_i \neq 0$.

Find the number of ways Joshjms can choose the order of fapping materials. As this number can be very large, output it modulo $M$.


### Input Format

Input will be given in the following format.
<pre>
F G H
N M
T S
g<sub>1</sub> g<sub>2</sub> g<sub>3</sub> … g<sub>G</sub>
h<sub>1</sub> h<sub>2</sub> h<sub>3</sub> … h<sub>H</sub>
m<sub>1</sub> m<sub>2</sub> m<sub>3</sub> … m<sub>H</sub>
</pre>
If $T =$ `g`, Joshjms starts at $g_S$. If $T =$ `h`, Joshjms starts at $h_S$.

### Output Format

Output a single integer denoting the number of ways Joshjms can choose the order of fapping materials modulo $M$.


### Constraints

- $1 \leq F, G, H \leq 1 \, 000$
- $1 \leq N \leq 9$
- $1 \leq M \leq 1 \, 000 \, 000 \, 000$
- $T$ is either `g` or `h`
- $1 \leq S \leq G$ if $T =$ `g`
- $1 \leq S \leq H$ if $T =$ `h`
- $1 \leq m_i \leq 10 \, 000$, for $1 \leq i \leq H$

### Subtasks

1. (3 points) $F \leq 2$
2. (6 points) $m_i = 1$
3. (11 points) $M = 2$
4. (35 points) $1 \leq F, G, H \leq 200$
5. (45 points) $G = 0, T =$ `h`