## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Palindrome Basis Solution | Codeforces Problem Solution 2022

C. Palindrome Basis
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

The first line of input contains a single integer $t$ ($1\le t\le {10}^{4}$) denoting the number of testcases.

Each testcase contains a single line of input containing a single integer $n$ ($1\le n\le 4\cdot {10}^{4}$) — the required sum of palindromic integers.

Output

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