变系数非波那契序列的定义如下:
$F_n~=~s_{n~-~1}\times F_{n~-~1}~+~s_{n~-~2}\times F_{n~-~2}$
其中
$F_0~=~0,~F_1~=~1$
序列s是一个无限的近似于循环长度为n的周期序列。也就是说对于大部分 $i\ge N$ , $s_i=s_{i~mod~N}$ 是成立的。
比如下面这个循环长度为4的近周期序列:
s = (5,3,8,11,5,3,7,11,5,3,8,11,…)
可以发现i=6的时候, $s_i=s_{i~mod~4}$ 并不成立 ( $s_6~=~7$ 而 $s_2~=~8$ )。
输入中会给出 $s_0,~s_1,~...,~s_{N~-~1}$ ,还有若干个 $s_i\ne s_{i~mod~N}$ 的位置及其具体值。
请计算 $F_K~mod~P$
Input
单组测试数据。
第一行有两个整数K和P(0≤K≤10^18,1≤P≤10^9)
第二行有一个整数N。(1≤N≤50000)
第三行有N个以空格分开的整数表示s序列的前N项。(1≤si≤10^9, i=0,1,...N-1)
第四行有一个整数M。(1≤M≤50000)
接下来M行每行有两个整数 j 和 v,表示 s[j]≠s[j mod N],并且s[j]=v。保证所有输入的j都是不一样的。(N≤j≤10^18, 1≤v≤10^9)
所有输入均为整数。
Output
输出F(K)对P取余的结果。
Sample Input
样例输入1
10 8
3
1 2 1
2
7 3
5 4
Sample Output
样例输出1
4