309400: CF1673C. Palindrome Basis
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Palindrome Basis
题意翻译
给你一个正整数。如果某个正整数的数字顺序颠倒后仍保持不变,那么我们将其称为无前导零的回文整数。 找出将 $n$ 表示为正回文整数和的不同方式的数量。如果至少一个回文整数的数量不同,则认为这两种方法不同。 例如:$5=4+1$ 和 $5=3+1+1$ 被认为是不同的,但 $5=3+1+1$ 和 $5=1+3+1$ 被认为是相同的。 你需要输出表示为 $n$ 的正回文整数和的不同方式的数量。 因为答案可能相当大,所以以模 $10^9+7$ 后输出即可题目描述
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 $ .
输入输出样例
输入样例 #1
2
5
12
输出样例 #1
7
74