Fibonotci

题意翻译

$\{ s_n \}_{n=0}^\infty$ 是一个正整数序列。 给定 $s_0,s_1, \dots ,s_{n-1}$，对于 $i \ge n$，有 $m$ 个 $i$ 给定 $s_i$，剩下的 $i$ 满足 $s_i = s_{i \bmod n}$。 $\{ f_n \}_{n=0}^\infty$ 同样是一个正整数序列。 $f_0 = 0,f_1 = 1$，对于 $i \ge 2$，$f_i = s_{i-1}f_{i-1} + s_{i-2}f_{i-2}$，求 $f_k \bmod p$。 $n,m \le 5 \times 10^4$，$k \le 10^{18}$，$s_i,p \le 10^9$。

题目描述

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 .

输入输出格式

输入格式

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<=10^{18} $ - $ 1<=P<=10^{9} $ - $ 1<=s_{i}<=10^{9} $ , for all $ i=0,1,...N-1 $ - $ N<=j<=10^{18} $ - $ 1<=v<=10^{9} $ - All values are integers

输出格式

Output should contain a single integer equal to .

输入输出样例

输入样例 #1

10 8
3
1 2 1
2
7 3
5 4

输出样例 #1

4