Palindrome Basis
Contest: Codeforces Round 785 (Div. 2)
Difficulty rating: 1500
Tags: brute force, dp, math, number theory

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

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
2
5
12

Example output:
7
74

Editorial:
First, we need to observe that the number of palindromes less than $$$4\cdot 10^4$$$ is relatively very small. The number of $$$5$$$-digit palindromes are $$$300$$$ (enumerate all $$$3$$$-digit numbers less than $$$400$$$ and append the first two digits in the reverse order). Similarly, the number of $$$4$$$-digit, $$$3$$$-digit, $$$2$$$-digit and $$$1$$$-digit palindromes are $$$90$$$, $$$90$$$, $$$9$$$ and $$$9$$$ respectively, giving a total of $$$M=498$$$ palindromes.
Now, the problem can be solved just like the classical partitions problem which can be solved using Dynamic Programming.
Let $$$dp_{k,m} =$$$ Number of ways to partition the number $$$k$$$ using only the first $$$m$$$ palindromes. It is not hard to see that $$$dp_{k,m} = dp_{k,m-1} + dp_{k-p_m,m}$$$ where $$$p_m$$$ denotes the $$$m^{th}$$$ palindrome. The first term corresponds to the partitions of $$$k$$$ using only the first $$$m-1$$$ palindromes and the second term corresponds to those partitions of $$$k$$$ in which the $$$m^{th}$$$ palindrome has been used atleast once. As base cases, $$$dp_{k,1}=1$$$ and $$$dp_{1,m}=1$$$. The final answer for any $$$n$$$ will be $$$dp_{n,M}$$$.
The time and space complexity is $$$\mathcal{O}(n\cdot M)$$$.
Bonus Task: Try to optimize the space complexity to $$$\mathcal{O}(n)$$$.