题目描述

我们用 \(\text{S}(N)\) 表示数 \(N\) 的数字和。编程计算，有多少对数 \(A,B\) 符合下列等式：\(\text{S}(A+B)=\text{S}(A)+\text{S}(B)\)，要求：数 \(A\) 和 \(B\) 的第一位不能为 \(0\)；当计算数对的总数时，与数 \(A\) 和 \(B\) 的顺序有关，比如，\((12,26)\) 和 \((26,12)\) 就是满足上述等式的不同的数对。

格式

输入格式

第一行为正整数 \(t(≤100)\)，表示数据组数；接下来 \(t\) 行，每行一个正整数 \(K(K≤10000)\)。

输出格式

对于每组数据，输出一个整数，表示有多少对 \(K\) 位的正整数 \(A\) 和 \(B\) 符合上述等式，由于结果比较大，输出结果对 \(10007\) 的余数。

样例1

输入样例1

2
2
10

输出样例1

1980
348

提示

在这里，即使是两个相同的数满足式子，例如，\(\text{S}(41+41)=\text{S}(41)+\text{S}(41)\)，这个也是算两个结论。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T3\)

文件IO

freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);