Bubble Cup V8 A Fibonotci

View as PDF

Submit solution


Points: 25
Time limit: 1.4s
Memory limit: 64M

Problem type

Fibonotci sequence is an integer recursive sequence defined by the recurrence relation

F_n = c_{n-1} \cdot F_{n-1} + c_{n-2} \cdot F_{n-2}

with

F_0 = 0, F_1 = 1.

Sequence c is infinite and almost cyclic sequence with a cycle of length N. A sequence s is almost cyclic with a cycle of length N iff s_i = s_{i \bmod N}, for i \ge N, except for a finite number of values s_i, for which s_i \ne s_{i \bmod N} (i \ge N).

Following is an example of an almost cyclic sequence with a cycle of length 4.

s = (5, 3, 8, 11, 5, 3, 7, 11, 5, 3, 8, 11, \dots)

Notice that the only value of s for which the equality s_i = s_{i \bmod 4} does not hold is s_6 (s_6 = 7 and s_2 = 8).

You are given c_0, c_1, \dots, c_{N-1} and all the values of sequence c for which c_i \ne c_{i \bmod N} (i \ge N).

Find F_K \bmod P.

Input Specification

The first line contains two numbers K and P. The second line contains a single number N. The third line contains N numbers separated by spaces, that represent the first N numbers of the sequence c. The fourth line contains a single number M, the number of values of sequence c for which c_i \ne c_{i \bmod N}. Each of the following M lines contains two integers j and v, indicating that c_j \ne c_{j \bmod N} and c_j = v.

Output Specification

Output should contain a single integer equal to F_K \bmod P.

Constraints

  • 1 \le N, M \le 50\,000
  • 0 \le K \le 10^{18}
  • 1 \le P \le 10^9
  • 1 \le c_i \le 10^9, for i = 0, 1, \dots, N-1
  • N \le j \le 10^{18}
  • 1 \le v \le 10^9
  • All values are integers

Sample Input

10 8
3
1 2 1
2
7 3
5 4

Sample Output

4

Comments

There are no comments at the moment.