P16125 [USTCPC 2026] Melody

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.

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$.

**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

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

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