Bubble Cup V8 A Fibonotci

View as PDF

Submit solution


Points: 25
Time limit: 3.0s
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 \geq N, except for a finite number of values s_i, for which s_i \neq s_{i \bmod N} (i \geq 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 \neq c_{i \bmod N} (i \geq 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 \neq c_{i \bmod N}. Each of the following M lines contains two integers j and v, indicating that c_j \neq c_{j \bmod N} and c_j = v.

Output Specification

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

Constraints

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

Example input

10 8
3
1 2 1
2
7 3
5 4

Example output

4

Comments

There are no comments at the moment.