CF575A.Fibonotci

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

F__n = s__n - 1·F__n - 1 + s__n - 2·F__n - 2

with

_F_0 = 0, _F_1 = 1

Sequence s is an infinite and almost cyclic sequence with a cycle of length N. A sequence s is called almost cyclic with a cycle of length N if , for i ≥ N, except for a finite number of values s__i, for which (i ≥ 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,…)

Notice that the only value of s for which the equality does not hold is _s_6 (_s_6 = 7 and _s_2 = 8). You are given _s_0, _s_1, ...s__N - 1 and all the values of sequence s for which (i ≥ N).

Find .

斐波诺契序列（Fibonotci 序列）是一个整数递归序列，其递推关系定义为：

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

初始条件为：

$$F_0 = 0,\quad F_1 = 1$$

序列 $s$ 是一个无限的、几乎循环（almost cyclic）序列，其循环节长度为 $N$。若对所有 $i \geq N$，均有 $s_i = s_{i \bmod N}$ 成立，仅有限个下标 $i$（满足 $i \geq N$）例外，则称序列 $s$ 是以 $N$ 为循环节长度的几乎循环序列；对这些例外位置 $i$，有 $s_i \ne s_{i \bmod N}$（其中 $i \geq N$）。

以下是一个循环节长度为 4 的几乎循环序列示例：

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

注意：唯一不满足等式 $s_i = s_{i \bmod N}$ 的项是 $s_6$（因为 $s_6 = 7$，而 $s_{6 \bmod 4} = s_2 = 8$）。
你将被给定 $s_0,\,s_1,\,\dots,\,s_{N-1}$，以及所有满足 $s_i \ne s_{i \bmod N}$ 的序列 $s$ 的项（其中 $i \geq N$）。

请计算：

$$F_K \bmod (10^9 + 7)$$

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 s. The fourth line contains a single number M, the number of values of sequence s for which . Each of the following M lines contains two numbers j and v, indicating that and s__j = v. All j-s are distinct.

• 1 ≤ N, M ≤ 50000
• 0 ≤ K ≤ 1018
• 1 ≤ P ≤ 109
• 1 ≤ s__i ≤ 109, for all i = 0, 1, ...N - 1
• N ≤ j ≤ 1018
• 1 ≤ v ≤ 109
• All values are integers

第一行包含两个数 $K$ 和 $P$。
第二行包含一个整数 $N$。
第三行包含 $N$ 个以空格分隔的数，表示序列 $s$ 的前 $N$ 项。
第四行包含一个整数 $M$，表示需指定值的序列 $s$ 的项数，即满足 的项数。
接下来的 $M$ 行中，每行包含两个数 $j$ 和 $v$，表示 且 $s_j = v$。所有 $j$ 均互不相同。

• $1 \leq N, M \leq 50000$
• $0 \leq K \leq 10^{18}$
• $1 \leq P \leq 10^9$
• $1 \leq s_i \leq 10^9$，对所有 $i = 0, 1, \dots, N-1$
• $N \leq j \leq 10^{18}$
• $1 \leq v \leq 10^9$
• 所有数值均为整数

Output should contain a single integer equal to .

输出应为一个整数，等于 。