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_{i \bmod N}~, for ~i \ge N~, except for a finite number of values ~s_i~, for which ~s_i \ne s_{i \bmod N}~ ~(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_{i \bmod 4}~ 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_{i \bmod N}~ ~(i \ge N)~.

Find ~F_K \bmod P~.

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_{i \bmod N}~. Each of the following ~M~ lines contains two integers ~j~ and ~v~, indicating that ~c_j \ne c_{j \bmod N}~ and ~c_j = v~.

Output Specification

Output should contain a single integer equal to ~F_K \bmod P~.

Constraints

• ~1 \le N, M \le 50\,000~
• ~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