『SpOI - R1』强大到让你们所有人注视

**本题包含多组测试。** 给定一个 $n$ 位的 $k$ 进制大数。 令 $S(l,r)$ 表示截取这个 $k$ 进制大数从高到低第 $l$ 位至第 $r$ 位构成的新 $k$ 进制数。 你需要求出 $\sum\limits_{1\leq l\leq r\leq n} S(l,r)$，注意这里的求和也建立在 $k$ 进制下。 由于答案可能很大，设 $(20070720)_{10}$ 在 $k$ 进制下是 $x$，你只需要输出答案对 $x$ 取模的结果。 **再次提醒：以上所有求和、运算和取值都建立在 $k$ 进制下。**

第一行一个整数 $T$，表示数据组数。 每组数据第一行两个正整数 $n,k$，表示这个大数。 每组数据第二行一个数列 $a$，从高位至低位依次表示这个大 $k$ 进制数的每一位上的数。保证 $\forall i\in[1,n],0\leq a_i<k$。

每组数据一行，表示答案对 $x$ 取模的结果。由于这也是一个 $k$ 进制数，所以用空格隔开依次输出每一位。 **注意你的输出中不应含有前导零。**

1
3 2
1 1 0

1 1 0 1

1
2 20070721
20070720 1

2

#### 样例 #1 解释 所有的 $S(l,r)$：$(1)_2,(1)_2,(0)_2,(11)_2,(10)_2,(110)_2$，把它们在 $2$ 进制下相加得到 $(1101)_2$，再在 $2$ 进制下对 $(20070720)_{10}=(1001100100100000101000000)_2$ 取模即可得到答案 $(1101)_2$。 #### 样例 #2 解释 对于这个数，$S(1,1)$ 显然被 $(\overline{20070720})_{20070721}$ 整除，$S(2,2),S(1,2)$ 被 $(\overline{20070720})_{20070721}$ 除后都余 $1$。所以取模后的答案是 $(2)_{20070721}$。 ### 数据范围 **本题开启子任务捆绑与子任务依赖。** 对于 $100\%$ 的数据，$1\leq T\leq 10$，$1\leq n\leq 5\times 10^5$，$0\leq a_i<k\leq 10^9$，$2\leq k\leq 10^9$。$k$ 进制大数可能含有前导零。 | Subtask | $T\leq$ | $n\leq$ | 特殊性质 | 得分 | 子任务依赖 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | 1 | $10$ | $100$ | 无 | $25$ | 无 | | 2 | $1$ | $5\times 10^3$ | $k>20070720$ | $20$ | 无 | | 3 | $1$ | $8\times 10^3$ | 无 | $25$ | 1,2 | | 4 | $5$ | $5\times 10^5$ | 无 | $30$ | 1,2,3 |