A5963. LibreOJ

**Source: [Codeforces Goodbye 2017 G. New Year and Original Order](https://codeforces.com/problemset/problem/908/G)**

LibreOJ 又锅了。

在锅了的 LibreOJ 中，一道题目的总得分通过如下方式计算：

1. 取出此题的所有提交记录，得到序列 **A**。

2. 对于 **A** 的每个元素，假设其得分为 $x$，对总得分的贡献为 $xf(x)$。

其中 $f(x)=\texttt{atoi(sort(itoa(x, b)), b)}$。

itoa(x, b) 表示将正整数 $x$ 以 $b$ 进制形式转换得到的字符串。

sort(s) 表示将字符串 $s$ 中的字符按照升序排序得到的字符串。

atoi(s, b) 表示将字符串 $s$ 以 $b$ 进制形式转换得到的正整数。

例如：
　itoa(184, 3) = "20211"
　sort("20211") = "01122"
　atoi("01122", 3) = 44
则当 $b=3$ 时 $f(184)=44$。

LibreOJ 的第 -1 题有着 $n$ 个提交记录，第 $i$ 个提交记录的得分为 $i$，请你求出第 -1 题的总得分。

形式化地说，你需要求出 $\displaystyle\sum_{i=1}^{n}if(i)$。

为了方便输出，你只需要求出答案对 $998,244,353$ 取模的结果即可。

**本题输入文件包含多组数据。**

第一行一个正整数 $T$，表示数据组数。

第二行一个正整数 $b$，意义见题目描述。

接下来每行表示一组数据。

每组数据一行一个**以 $b$ 进制形式表示**的正整数 $n$，意义见题目描述。

对于每组数据，输出一行一个整数表示答案。

定义 $\mathrm{Len}=T+\sum\lfloor\log_b(n)\rfloor$。

对于所有测试点：$T\le 20$，$2\le b\le 10$，$n\le 10^{1000}$，$\mathrm{Len}\le 1000$。

每个测试点的具体限制见下表：

| 测试点编号 | $n\le$ | $\mathrm{Len}\le$ | $T=$ | $b=2$ |
| :--: | :--: | :--: | :--: | :--: |
| $1\sim2$ | $10^5$ | $5$ | $1$ | 不保证 |
| $3\sim4$ | $10^5$ | $340$ | $20$ | 不保证 |
| $5\sim8$ | $10^{1000}$ | $1000$ | $1$ | 不保证 |
| $9\sim10$ | $10^{1000}$ | $1000$ | $1$ | 保证 |
| $11\sim14$ | $10^{1000}$ | $1000$ | $10$ | 保证 |
| $15\sim20$ | $10^{1000}$ | $1000$ | $10$ | 不保证 |


----

**Author: PinkRabbit**