Palindrome Basis Solution | Codeforces Problem Solution 2022

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$5=4+1$ and 5=3+1+1$5=3+1+1$ are considered different but 5=3+1+1$5=3+1+1$ and 5=1+3+1$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$.

Solution Click Below:- CLICK HERE

Since the answer can be quite large, print it modulo 109+7${10}^9+7$.

Lost Arithmetic Progression Solution | Codeforces Problem Solution 2022

Power or XOR? Solution | Codeforces Problem Solution 2022 

Anti-Theft Road Planning Solution | Codeforces Problem Solution 2022 

A Perfectly Balanced String? Solution | Codeforces Problem Solution 2022 

Palindrome Basis Solution | Codeforces Problem Solution 2022 

Subtle Substring Subtraction Solution | Codeforces Problem Solution 2022 

Input

The first line of input contains a single integer 𝑡$t$ (1≤𝑡≤104$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≤𝑛≤4⋅104$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 109+7${10}^9+7$.

Join Now for Solution:-