题目描述

$\{ s_n \}_{n=0}^\infty$ 是一个正整数序列。

给定 $s_0,s_1, \dots ,s_{n-1}$，对于 $i \ge n$，有 $m$ 个 $i$ 给定 $s_i$，剩下的 $i$ 满足 $s_i = s_{i \bmod n}$。

$\{ f_n \}_{n=0}^\infty$ 同样是一个正整数序列。

$f_0 = 0,f_1 = 1$，对于 $i \ge 2$，$f_i = s_{i-1}f_{i-1} + s_{i-2}f_{i-2}$，求 $f_k \bmod p$。

$n,m \le 5 \times 10^4$，$k \le 10^{18}$，$s_i,p \le 10^9$。

输入格式

第一行两个整数 $k$，$p$。

第二行一个整数 $n$。

第三行 $n$ 个整数 $s_i$。

第四行一个整数 $m$。

接下来 $m$ 行，每行两个整数 $i$，$v$，表示令 $s_i = v$。

输出格式

一个整数表示答案。

10 8
3
1 2 1
2
7 3
5 4

4