# [Solution] Palindrome Basis solution codeforces

Palindrome Basis solution codeforces – 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+15=4+1 and 5=3+1+15=3+1+1 are considered different but 5=3+1+15=3+1+1 and 5=1+3+15=1+3+1 are considered the same.

## [Solution] Palindrome Basis solution codeforces

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 109+7109+7.

Input

The first line of input contains a single integer 𝑡t (1𝑡1041≤t≤104) denoting the number of testcases.

Each testcase contains a single line of input containing a single integer 𝑛n (1𝑛41041≤n≤4⋅104) — the required sum of palindromic integers.

## [Solution] Palindrome Basis solution codeforces

For each testcase, print a single integer denoting the required answer modulo 109+7109+7.

Example
input

Copy
2
5
12

output

Copy
7
74


## Palindrome Basis solution codeforces

For the first testcase, there are 77 ways to partition 55 as a sum of positive palindromic integers:

• 5=1+1+1+1+15=1+1+1+1+1
• 5=1+1+1+25=1+1+1+2
• 5=1+2+25=1+2+2
• 5=1+1+35=1+1+3
• 5=2+35=2+3
• 5=1+45=1+4
• 5=55=5

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