CF1673C.Palindrome Basis

You are given a positive integer $n$. Let's call some positive integer $a$ without leading zeroes palindromic if it remains the same after reversing the order of its digits. Find the number of distinct ways to express $n$ as a sum of positive palindromic integers. Two ways are considered different if the frequency of at least one palindromic integer is different in them. For example, $5=4+1$ and $5=3+1+1$ are considered different but $5=3+1+1$ and $5=1+3+1$ are considered the same.

Formally, you need to find the number of distinct multisets of positive palindromic integers the sum of which is equal to $n$.

Since the answer can be quite large, print it modulo $10^9+7$.

给你一个正整数 $n$。我们称一个不含前导零的正整数 $a$ 为回文数，如果将其各位数字顺序反转后，所得数与原数相同。请你求出将 $n$ 表示为若干个正回文数之和的不同方式的数目。若两种表示方式中至少存在一个回文数的出现频次不同，则认为它们是不同的表示方式。例如，$5=4+1$ 和 $5=3+1+1$ 被视为不同，但 $5=3+1+1$ 和 $5=1+3+1$ 被视为相同。

形式化地说，你需要计算满足以下条件的正回文数多重集的个数：该多重集中所有元素之和等于 $n$。

由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

The first line of input contains a single integer $t$ ($1\leq t\leq 10^4$) denoting the number of testcases.

Each testcase contains a single line of input containing a single integer $n$ ($1\leq n\leq 4\cdot 10^4$) — the required sum of palindromic integers.

输入的第一行包含一个整数 $t$（$1\leq t\leq 10^4$），表示测试用例的数量。

每个测试用例包含一行输入，其中包含一个整数 $n$（$1\leq n\leq 4\cdot 10^4$）——即所需表示为回文数之和的目标值。

For each testcase, print a single integer denoting the required answer modulo $10^9+7$.

对于每个测试用例，输出一个整数，表示所求答案对 $10^9+7$ 取模的结果。

For the first testcase, there are $7$ ways to partition $5$ as a sum of positive palindromic integers:

• $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$

For the second testcase, there are total $77$ ways to partition $12$ as a sum of positive integers but among them, the partitions $12=2+10$, $12=1+1+10$ and $12=12$ are not valid partitions of $12$ as a sum of positive palindromic integers because $10$ and $12$ are not palindromic. So, there are $74$ ways to partition $12$ as a sum of positive palindromic integers.

对于第一个测试用例，将 $5$ 拆分为若干个正回文整数之和共有 $7$ 种方式：

• $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$

对于第二个测试用例，将 $12$ 拆分为若干个正整数之和共有 $77$ 种方式；但其中，拆分 $12=2+10$、$12=1+1+10$ 和 $12=12$ 并非将 $12$ 拆分为若干个正回文整数之和的有效拆分，因为 $10$ 和 $12$ 均不是回文数。因此，将 $12$ 拆分为若干个正回文整数之和共有 $74$ 种方式。