给你一个正整数$$$n$$$。如果某个不带前导零的正整数 $$$a$$$ 在颠倒其数字顺序后保持不变,我们称其为回文。找出将 $$$n$$$ 表示为正回文整数之和的不同方法的数量。如果两种方式中至少有一个回文整数出现的频率不同,则认为两种方式不同。例如,$$$5=4+1$$$ 和 $$$5=3+1+1$$$ 被视为不同,但 $$$5=3+1+1$$$ 和 $$$5=1+3+1$$$ 被视为相同。
形式上,您需要找到总和等于 $$$n$$$ 的正回文整数的不同多重集的数量。
由于答案可能相当大,因此打印它对 $$$10^9+7$$$ 取模。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) 表示测试用例的数量。
每个测试用例包含一行输入,其中包含一个整数 $$$n$$$ ($$$1\leq n\leq 4\cdot 10^4$$$) — 所需的回文整数之和。
输出
对于每个测试用例,打印一个整数,表示所需答案以 $$$10^9+7$$$ 为模。
示例
输入 #1
2 5 12
输出 #1
7 74
注意
对于第一个测试用例,有 $$$7$$$ 方法将 $$$5$$$ 划分为正回文整数之和:
- $$$5=1+1+1+1+1$$$
- $$$5=1+1+1+2$$$
- $$$5=1+2+2$$$
- $$$5=1+1+3$$$
- $$$5=2+3$$$
- $$$5=1+4$$$
- $$$5=5$$$
对于第二个测试用例,总共有 $$$77$$$ 方法将 $$$12$$$ 划分为正整数之和,但其中分区 $$$12=2+10$$$、$$$12=1+1+10$$$ 和 $$$12=12$$$ 不是 $$$12$$$ 作为正整数之和的有效分区回文整数,因为 $$$10$$$ 和 $$$12$$$ 不是回文整数。因此,有 $$$74$$$ 方法将 $$$12$$$ 划分为正回文整数之和。