Palindrome Basis
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
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$.
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.
For each testcase, print a single integer denoting the required answer 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$.
2
5
12
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.
20240122 CF div2.1673
- Status
- Done
- Rule
- IOI
- Problem
- 6
- Start at
- 2024-1-22 14:30
- End at
- 2024-1-22 17:30
- Duration
- 3 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 13