C. Palindrome Basistime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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.OutputFor each testcase, print a single integer denoting the required answer modulo 10^9+7.ExampleInput
2
5
12
Output
7
74
NoteFor 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.
2
5
12

7 74 
['brute force', 'dp', 'math', 'number theory', '*1500']