You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

坂井和奏想要完成当年和母亲没有写完的歌。她找到了不完整的旋律，想将它谱成一首优美和谐的乐曲。

题目描述

一段旋律的长度为 $n$，由 $k$ 种不同音符组成，即每个音符 $a_1,\dots,a_n$ 均为 $1$ 到 $k$ 中的一个整数。$k$ 种音符构成了一个平均律，相邻两个音符 $a_i,a_{i+1}$ 之间会构成一个大小为 $(a_{i+1}-a_i)\bmod k$ 的进行。

和奏有一个进行的和谐度表 $h_0,\dots,h_{k-1}$，表示大小为 $i$ 的进行的和谐度为 $h_i$。

她认为在一段旋律中，相同大小的进行反复出现时，其和谐度是幂次级叠加的，即若一段旋律中有 $c_i$ 个大小为 $i$ 的进行，则它们总的和谐度为 $h_i^{c_i}$。特别地，她认为 $0^0=1$。

她认为旋律中不同大小的进行之间和谐度是简单叠加的，即整段旋律的和谐度为 $\sum_{i=0}^{k-1}h_i^{c_i}$。

现在她找到了那份不完整的旋律，其中有 $m$ 个音符已经确定，分别为 $a_{x_i}=y_i$。和奏想请你求出，如果她可以任意选择其余 $n-m$ 个音符，得到的 $k^{n-m}$ 种不同旋律的和谐度之和是多少。由于答案可能很大，你只需要帮她求出其对 $20120923$ 取模的值。

输入格式

本题有多组测试数据。

首先输入一行，包含一个整数 $T$（$1\le T\le 10^5$），表示测试数据组数。

每组数据首先输入一行，包含三个整数，表示旋律长度 $n$（$1\le n\le 10^9$），已确定音符数 $m$（$0\le m\le 10^6$）和音符种类数 $k$（$1\le k\le 10^6$）。

接下来输入一行，包含一个长度为 $k$ 的数组，依次表示 $h_0,\dots,h_{k-1}$。保证 $0\le h_i<20120923$。

接下来输入 $m$ 行，每行包含两个整数 $x_i,y_i$，表示 $a_{x_i}=y_i$。保证 $1\le x_i\le n$，$1\le y_i\le k$，且 $x_i$ 互不相同。

保证 $\sum k\le 10^6$，$\sum mk\le 10^6$。

输出格式

输出 $T$ 行，每行一个整数，表示答案取模 $20120923$ 后的结果。

样例 #1

样例输入 #1

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

样例输出 #1

14667
3100924
13878903

提示

对于第二组数据，一种可能的完整旋律为：$[5,1,1,2,3,5,5,6,1,7,1,2,3]$，其中 $c_0=2,c_1=6,c_2=2,c_3=1,c_4=c_5=0,c_6=1$，因此其和谐度为 $1^2+2^6+2^2+2^1+0^0+1^0+0^1=73$。