← 返回题目列表

Codeforces · 575/A

A. 斐波诺契

中文机器翻译题面 查看原题

斐波诺契序列是由递归关系定义的整数递归序列

Fn = sn - 1·Fn - 1 + sn - 2·Fn - 2

F0 = 0,F1 = 1

序列 s 是一个无限且几乎循环的序列,其周期长度为 N。如果 $$s_{i} = s_{i \bmod N}$$,且 i ≥ N,则序列 s 称为周期长度为 N 的几乎循环序列,但有限数量的值 si 除外,其中 $$s_i \neq s_{i \bmod N}$$ (i ≥ N)。

以下是周期长度为 4 的几乎循环序列的示例:

s = (5,3,8,11,5,3,7,11,5,3,8,11,…)

请注意,等式 $$s_{i} = s_{i \bmod 4 }$$ 不成立的 s 的唯一值是 s6(s6 = 7 且 s2 = 8)。给定 s0、s1、...sN - 1 以及 $$s_i \neq s_{i \bmod N}$$ (i ≥ N) 的序列 s 的所有值。

查找 $$F_{K} \bmod P$$。

输入

第一行包含两个数字 K 和 P。第二行包含一个数字 N。第三行包含由空格分隔的 N 个数字,表示序列 s 的前 N ​​个数字。第四行包含一个数字 M,即 $$s_i \neq s_{i \bmod N}$$ 的序列 s 的值的数量。接下来的 M 行每行包含两个数字 j 和 v,表示 $$s_j \neq s_{j \bmod N}$$ 和 sj = v。所有 j-s 都是不同的。

- 1 ≤ N, M ≤ 50000
- 0 ≤ K ≤ 1018
- 1 ≤ P ≤ 109
- 1 ≤ si ≤ 109,对于所有 i = 0, 1, ...N - 1
- N ≤ j ≤ 1018
- 1 ≤ v ≤ 109
- 所有值均为整数

输出

输出应包含等于 $$F_{K} \bmod P$$ 的单个整数。

示例

输入 #1

10 8
3
1 2 1
2
7 3
5 4

输出 #1

4