P10791 『SpOI - R1』So Powerful That You All Must Watch

**This problem contains multiple test cases.** You are given an $n$-digit base-$k$ big number. Let $S(l,r)$ denote the new base-$k$ number formed by taking the digits from the $l$-th to the $r$-th digit (from most significant to least significant) of this base-$k$ number. You need to compute $\sum\limits_{1\leq l\leq r\leq n} S(l,r)$. Note that this summation is also done in base $k$. Since the answer may be very large, let $(20070720)_{10}$ be $x$ when written in base $k$. You only need to output the result of the answer modulo $x$. **Reminder again: all summations, operations, and modulo in this problem are done in base $k$.**

The first line contains an integer $T$, the number of test cases. For each test case, the first line contains two positive integers $n,k$, describing this big number. The second line of each test case contains a sequence $a$, which gives each digit of this base-$k$ big number from most significant to least significant. It is guaranteed that $\forall i\in[1,n],0\leq a_i

For each test case, output one line: the answer modulo $x$. Since it is also a base-$k$ number, output each digit in order separated by spaces. **Note that your output should not contain leading zeros.**

#### Explanation for Sample #1 All $S(l,r)$ are: $(1)_2,(1)_2,(0)_2,(11)_2,(10)_2,(110)_2$. Adding them in base $2$ gives $(1101)_2$, and then taking modulo $(20070720)_{10}=(1001100100100000101000000)_2$ in base $2$ yields the answer $(1101)_2$. #### Explanation for Sample #2 For this number, $S(1,1)$ is clearly divisible by $(\overline{20070720})_{20070721}$. After dividing $S(2,2)$ and $S(1,2)$ by $(\overline{20070720})_{20070721}$, both remainders are $1$. Therefore, the answer after modulo is $(2)_{20070721}$. ### Constraints **This problem uses bundled subtasks and subtask dependencies.** For $100\%$ of the testdata, $1\leq T\leq 10$, $1\leq n\leq 5\times 10^5$, $0\leq a_i20070720$ | $20$ | None | | 3 | $1$ | $8\times 10^3$ | None | $25$ | 1,2 | | 4 | $5$ | $5\times 10^5$ | None | $30$ | 1,2,3 | Translated by ChatGPT 5