题目描述

本题包含多组测试。

给定一个 $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$ 进制大数可能含有前导零。