题意：
定义类循环序列为 长度无限，且除了有限个元素外，均满足s[i] ≡ s[i mod N] (i≥N)。
现在有数列F，定义为 F[i] = s[i-2]*F[i-1] + s[i-1]*F[i-1]，特别的，F[0] = 0, F[1] = 1。
给定正整数K,P,N代表要求输出的答案为F[k] mod P，类循环序列s的长度为N。
接下来给出s[0]..s[n-1]。
然后是一个正整数M，代表不满足循环条件的元素个数。
接下来M行每行两个正整数j,v表示s[j] = v，保证所有j不同。
1<=N,M<=10^5,
1<=P,s[i],v<=10^9,
1<=K,j<=10^18
题解：
会矩阵乘法快速转移的一看就知道大概的做法…所以思考难度不算高。
但是实现起来比较麻烦。
可以明显地看出，没有被特殊位置影响到递推式的部分可以快速转移。
所以我们排序并求出所有被特殊位置影响到递推式的位置（即特殊位置的后两个位置）。
然后按照排序相邻的两个受影响位置的位置关系分类来做：
1、两个受影响位置分离，中间包含若干个循环
那么我们可以在预处理时求出一个循环内所有转移矩阵的乘积，
然后找出当前位置所处的循环节末尾，下一个位置所处的循环节开头，
把这中间的部分用快速幂处理出来。
而当前位置到循环节末的部分，可以用反向的前缀和或线段树处理。
循环节头到下一个位置的部分，可以用前缀和或线段树处理。
（这里用前缀和是O(1)，但是因为还有快速幂，总的复杂度没有降低）
2、两个受影响位置分离，在同一循环节之中
这种情况可以直接用线段树求处理出区间的乘积。
3、两个受影响位置相邻
直接暴力计算。
这种做法不用考虑连续的受影响位置跨越循环节的情况，写起来比较方便，不那么容易写挂。
（然而我因为诸如没开long long这类的低级错误挂了很多次）
时间复杂度O( (2^3) * M log N )
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = , NS = +;
typedef long long lint;
typedef pair<lint,int> pli;
inline int read()
{
int s = ; char c; while((c=getchar())<'0'||c>'9');
do{s=s*+c-'0';}while((c=getchar())>='0'&&c<='9');
return s;
}
inline lint readll()
{
lint s = ;char c; while((c=getchar())<'0'||c>'9');
do{s=s*+c-'0';}while((c=getchar())>='0'&&c<='9');
return s;
}
int n,m,p,s[N],br[N+N],cr[N+N],cur,S,tot;
lint k,ar[N+N];
pli q[N];
struct mrx
{
int n[][];
void clr(){ memset(n,,sizeof n); }
friend mrx operator * (const mrx &a,const mrx &b)
{
mrx c; c.clr();
for(int i=;i<;i++) for(int k=;k<;k++) if(a.n[i][k]) for(int j=;j<;j++)
c.n[i][j] = ((lint)c.n[i][j]+(lint)a.n[i][k]*b.n[k][j])%p;
return c;
}
}ym,tm[N],stm,I,tmpm,tr[NS],psm[N],ssm[N];
inline lint mo(lint a){ return (a+n-)%n+; }
mrx powmod(mrx a,lint b)
{
mrx ans = I;
for(;b;b>>=)
{
if(b&) ans = ans*a;
a = a*a;
}
return ans;
}
mrx query(int l,int r)
{
if(l>r) return I;
mrx ls = I, rs = I;
for(l=l+S-,r=r+S+;l^r^;l>>=,r>>=)
{
if(~l&) ls = ls*tr[l^];
if( r&) rs = tr[r^]*rs;
}
return ls*rs;
}
int calc()
{
int i;
for(i=;i<=m;i++)
{
if(q[i].first>=k) break;
ar[++tot] = q[i].first+;
br[tot] = (q[i].first==q[i-].first+)?q[i-].second:s[(q[i].first+n-)%n+];
cr[tot] = q[i].second;
if(q[i].first+!=q[i+].first&&q[i].first+<=k)
ar[++tot] = q[i].first+, br[tot] = cr[tot-], cr[tot] = s[(q[i].first+)%n+];
}
tmpm = tm[];
cur = ; while(cur<=tot&&ar[cur]<) cur++;
ar[--cur] = ;
ar[++tot] = k+;
lint ql,qr;
for(;cur<tot;cur++)
{
if(cur+!=tot&&ar[cur+]==ar[cur]+)
{
tmpm.n[][] = br[cur+], tmpm.n[][] = cr[cur+];
ym = ym*tmpm;
continue;
}
ql = (lint)((ar[cur]-)/n)*n+n;
qr = (lint)((ar[cur+]-)/n)*n+;
if(ql<qr)
ym = ((ym * ssm[(ar[cur]-)%n+]) * powmod(psm[n],(qr-ql-)/n)) * psm[ar[cur+]-qr];
else
ym = ym * query(mo(ar[cur]+),mo(ar[cur+]-));
if(cur+==tot) break;
tmpm.n[][] = br[cur+], tmpm.n[][] = cr[cur+];
ym = ym*tmpm;
}
return ym.n[][];
}
int main()
{
int i;
k = readll(), p = read();
if(k<){ printf("%d\n",(int)k%p); return ; }
for(i=,n=read();i<=n;i++) s[i] = read();
for(S=;S<=n+;S<<=);
s[n+] = s[];
ym.n[][] = ; I.n[][] = I.n[][] = ; psm[] = ssm[n+] = I;
for(i=;i<=n;i++)
{
tm[i].n[][] = ;
tm[i].n[][] = s[(i+n*-)%n+];
tm[i].n[][] = s[(i+n*-)%n+];
tr[S+i] = tm[i];
psm[i] = psm[i-] * tm[i];
}
for(i=n;i>=;i--) ssm[i] = tm[i] * ssm[i+];
for(i=S;i>=;i--) tr[i] = tr[i+i] * tr[i+i+];
for(i=,m=read();i<=m;i++) q[i].first = readll(), q[i].second = read();
q[].first = q[m+].first = -;
sort(q+,q++m);
printf("%d\n",calc());
return ;
}