# [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â‰¤đť‘›â‰¤4â‹…1041â‰¤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+10,Â 12=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.