UOJ Logo hszxoizjn的博客

博客

标签
暂无

Problem B

2018-08-09 20:12:07 By hszxoizjn

变系数非波那契序列的定义如下:

$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

共 1 篇博客