#P18689. Digit Mode

    ID: 18025 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-数位 DP上界限制状态指数生成函数生成函数求系数多项式求逆截断幂级数阶乘逆元预处理增量维护

Digit Mode

Digit Mode

对于正整数 xx,令 m(x)m(x) 表示其十进制表示中所有数字的众数。众数是出现次数最多的数字;如果多个数字的出现次数并列最多,则选择其中最大的数字。例如:m(15532)=5m(15532)=5,m(25252)=2m(25252)=2,m(103000)=0m(103000)=0,m(364364)=6m(364364)=6,m(114514)=1m(114514)=1,m(889464)=8m(889464)=8。

给定一个正整数 nn,DreamGrid 想知道

(∑x=1nm(x)) mod (109+7)\left(\sum_{x=1}^{n}m(x)\right)\bmod(10^9+7)

的值。

输入格式

输入包含多组测试用例。第一行包含一个整数 TT,表示测试用例数。

对于每个测试用例,第一行包含一个没有前导零的正整数 nn(1≤n<10501\le n<10^{50})。

保证整个输入中所有测试用例的 ∣n∣|n| 之和不超过 5050,其中 ∣n∣|n| 表示 nn 的十进制位数。

输出格式

对于每个测试用例,输出一行,包含一个整数,表示 (∑x=1nm(x)) mod (109+7)\left(\sum_{x=1}^{n}m(x)\right)\bmod(10^9+7)。

样例 1 输入

5
9
99
999
99999
999999

样例 1 输出

45
615
6570
597600
5689830