Codeforces Round 785 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

dp

math

number theory

*1500

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Palindrome Basis

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Input

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

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

Example

Input

2512

Output

7 74

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/19/2024 18:15:49 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|