回文数基

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个正整数 $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

数据范围

对于所有数据，$1\le t\le10^4$，$1\le n\le4\times10^4$。答案对 $10^9+7$ 取模。