问题描述 Description
现定义序列它的第i项为： Fi=Si−1∗Fi−1+Si−2∗Fi−2 定义F0=0以及F1=1 其中，S是一个无限长的，几乎循环的一个数字序列，它的循环节长度为N，也就是说，通常会有Si=SimodN。但是S中也存在少数元素并不符合这个循环节，也就是说，会有若干个元素，Si≠SimodN。 现在给出序列S的循环节，以及S中不符合循环的位置以及值，求FkmodP。
输入 Input
输入文件的第一行有两个整数K和P。 第二行是一个整数N。 第三行包含N个正整数，表示循环节中所有的数字。 接下来一行是一个整数M。接下来的M行，每行包含两个整数x和y，表示在序列S中不符合循环节的位置以及相应位置上的值，即Sx=y。
输出 Output
输出文件包含一个整数，即相应输入文件的答案。
样例输入 Sample Input
42 1248493 5 5 2 4 1 6 5 9 3 8 4 21 21 10 18 24 10
样例输出 Sample Output
232959
限制 Limits
对于30%的数据：0≤k≤10000,1≤n≤1000,1≤M≤20； 对于70%的数据：0≤k≤1018,1≤n≤1000,1≤M≤20； 对于100%的数据：0≤k≤1018,1≤n,m≤5×104,1≤p≤109,1≤Si≤109,n≤x≤1018,1≤y≤109 。 Time Limit : 2s & Memory Limit : 128MB
一看k这么大快速幂逃不掉了…… 一看递推关系矩阵逃不掉了…… 所以矩阵快速幂逃不掉了。 MDZZ怎么搞矩阵？ 这回在化学课上推公式…… f0=0f1=1f2=s1f1=s1f3=s2f2+s1f1=s1s2+s1f4=s3f3+s2f2=s1s2s3+s1s2+s1s3...... 看出什么来了吗？ 反正我看了一天 可以看出这个f只与s有关…… 假如能搞出一个矩阵的话，可以借鉴分块思想，将一个循环节看成一个块，将整个块内的值求出后，跑矩阵快速幂，之后零散部分暴力。 可是有修改…… 就将修改看成断点，假如断点处于同一块内，暴力即可，如果不在，零散暴力，整块快速幂。 时间为O(mnlogk) 这样可以过70%…… 100%优化的是零散部分，因为要不停计算零散部分，这些零散部分还是循环的，所以可以用线段树优化。 时间为O(mlognlogk) 所以，怎么构造矩阵？ 还是两个矩阵，一个是处理影响的，一个是统计答案的。 统计答案的矩阵是一个1×2的矩阵： [fa+1fa] 当然也可以写成2×2的，其余补0即可。 处理影响的矩阵是一个2×2的矩阵： [01sasa+1] 遇到断点答案矩阵暴力乘矩阵即可，此矩阵为： [01sx−1c] 其中x为需要修改的位置，c为变换成的数。 这还没完，因为矩阵与x+1位置也有关，还需要乘： [01csx+1] 这样就可以了 还有一些许多细节需要注意……具体参见代码。 Code
