A14990. 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$ .

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.

For each testcase, print a single integer denoting the required answer modulo $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.