Background

Sakai Kanade wants to finish the song that she and her mother did not complete that year. She found an incomplete melody and wants to arrange it into a beautiful and harmonious piece of music.

Problem Description

A melody has length $n$ and consists of $k$ different notes. That is, each note $a_1,\dots,a_n$ is an integer from $1$ to $k$. The $k$ notes form an equal temperament. Between two adjacent notes $a_i,a_{i+1}$, a transition is formed with size $(a_{i+1}-a_i)\bmod k$.

Kanade has a harmony table for transitions $h_0,\dots,h_{k-1}$, where the harmony value of a transition of size $i$ is $h_i$.

She believes that when transitions of the same size appear repeatedly in a melody, their harmony values combine by exponentiation. That is, if a melody contains $c_i$ transitions of size $i$, then their total harmony value is $h_i^{c_i}$. In particular, she defines $0^0=1$.

She believes that harmony values of transitions of different sizes combine by simple addition. That is, the harmony of the whole melody is $\sum_{i=0}^{k-1}h_i^{c_i}$.

Now she has found that incomplete melody, in which $m$ notes are already fixed as $a_{x_i}=y_i$. Kanade wants you to compute: if she can choose the remaining $n-m$ notes arbitrarily, what is the sum of harmony values over all $k^{n-m}$ different complete melodies? Since the answer may be very large, you only need to output it modulo $20120923$.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$ ($1\le T\le 10^5$), the number of test cases.

For each test case, the first line contains three integers: the melody length $n$ ($1\le n\le 10^9$), the number of fixed notes $m$ ($0\le m\le 10^6$), and the number of note types $k$ ($1\le k\le 10^6$).

The next line contains an array of length $k$, giving $h_0,\dots,h_{k-1}$ in order. It is guaranteed that $0\le h_i<20120923$.

Then follow $m$ lines, each containing two integers $x_i,y_i$, meaning $a_{x_i}=y_i$. It is guaranteed that $1\le x_i\le n$, $1\le y_i\le k$, and all $x_i$ are distinct.

It is guaranteed that $\sum k\le 10^6$, $\sum mk\le 10^6$.

Output Format

Output $T$ lines. Each line contains one integer, the answer modulo $20120923$.

3
7 0 3
0 1 2
13 3 7
1 2 2 2 0 1 0
2 1
10 7
7 5
1000000000 10 12
2 0 3 2 1 3 0 3 2 1 1 0
1 0
10 1
100 2
1000 3
10000 4
100000 5
1000000 6
10000000 7
100000000 8
1000000000 9

14667
3100924
13878903

Hint

For the second test case, one possible complete melody is: $[5,1,1,2,3,5,5,6,1,7,1,2,3]$. In this melody, $c_0=2,c_1=6,c_2=2,c_3=1,c_4=c_5=0,c_6=1$, so its harmony is $1^2+2^6+2^2+2^1+0^0+1^0+0^1=73$.

Translated by ChatGPT 5