Fibonotci sequence is an integer recursive sequence defined by the recurrence relation

$F_n=c_{n-1}\cdot F_{n-1}+c_{n-2}\cdot F_{n-2}$

with

$F_0=0,F_1=1$.

Sequence $c$ is infinite and almost cyclic sequence with a cycle of length $N$. A sequence $s$ is almost cyclic with a cycle of length $N$ iff $s_i=s_{imodN}$, for $i\ge N$, except for a finite number of values $s_i$, for which $s_i\ne s_{imodN}$ $(i\ge N)$.

Following is an example of an almost cyclic sequence with a cycle of length $4$.

$s=(5,3,8,11,5,3,7,11,5,3,8,11,\dots )$

Notice that the only value of $s$ for which the equality $s_i=s_{imod4}$ does not hold is $s_6$ ($s_6=7$ and $s_2=8$).

You are given $c_0,c_1,\dots ,c_{N-1}$ and all the values of sequence $c$ for which $c_i\ne c_{imodN}$ $(i\ge N)$.

Find $F_{K}modP$.

Input Specification

The first line contains two numbers $K$ and $P$. The second line contains a single number $N$. The third line contains $N$ numbers separated by spaces, that represent the first $N$ numbers of the sequence $c$. The fourth line contains a single number $M$, the number of values of sequence $c$ for which $c_i\ne c_{imodN}$. Each of the following $M$ lines contains two integers $j$ and $v$, indicating that $c_j\ne c_{jmodN}$ and $c_j=v$.

Output Specification

Output should contain a single integer equal to $F_{K}modP$.

Constraints

• $1\le N,M\le 50000$
• $0\le K\le {10}^{18}$
• $1\le P\le {10}^9$
• $1\le c_i\le {10}^9$, for $i=0,1,\dots ,N-1$
• $N\le j\le {10}^{18}$
• $1\le v\le {10}^9$
• All values are integers

Sample Input

10 8
3
1 2 1
2
7 3
5 4

Sample Output

4