1673C.md (1862B)
1 Source: https://codeforces.com/problemset/problem/1673/C 2 3 C. Palindrome Basis 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 Formally, you need to find the number of distinct multisets of positive palindromic integers the sum of which is equal to $n$. 24 25 Since the answer can be quite large, print it modulo $10^9+7$. 26 27 Input 28 29 The first line of input contains a single integer $t$ ($1\leq t\leq 10^4$) denoting the number of testcases. 30 31 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. 32 33 Output 34 35 For each testcase, print a single integer denoting the required answer modulo $10^9+7$. 36 37 Example 38 39 Input 40 41 ``` 42 2 43 44 5 45 46 12 47 ``` 48 49 Output 50 51 ``` 52 7 53 74 54 ``` 55 56 Note 57 58 For the first testcase, there are $7$ ways to partition $5$ as a sum of positive palindromic integers: 59 60 * $5=1+1+1+1+1$ 61 * $5=1+1+1+2$ 62 * $5=1+2+2$ 63 * $5=1+1+3$ 64 * $5=2+3$ 65 * $5=1+4$ 66 * $5=5$ 67 68 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.