P16125 [USTCPC 2026] Melody

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

一段旋律的长度为 $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

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

对于第二组数据，一种可能的完整旋律为：$[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$。