题意：给出一个数，问将他分成一些回文数（数字可以相同），问有多少种方案，方案数模一个大质数。
分析：回文数可以无限选，所以这是一道有完全背包问题，所以只需预处理出4e4以内的回文数，\(f_{j}\)表示背包容量为j的放置方案数，数位状态转移\(f_{j} = f_{j} + f_{j - h[i]}\)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int mod = 1e9 + 7, INF = 1 << 30;
const int N = 4e4 + 10;
vector<int> h(1, 1);
int sz = 0;
int f[N];
void init()
{
for (int i = 1; i <= N; i ++){
if (i <= 9) {h.push_back(i); sz ++;}
else{
int len = 0;
vector<int> w(6);
int x = i;
while (x){
w[++ len] = x % 10;
x /= 10;
}
bool ok = 1;
for (int j = 1; j <= len / 2; j ++) ok &= (w[j] == w[len + 1 - j]);
if (ok) {h.push_back(i); sz ++;}
}
}
}
void solve()
{
f[0] = 1;
for (int i = 1; i <= sz; i ++){
for (int j = h[i]; j <= N; j ++){
f[j] = (f[j] + f[j - h[i]]) % mod;
}
}
}
int main()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
init();
solve();
int t;
cin >> t;
while(t --){
int n;
cin >> n;
cout << f[n] << endl;
}
return 0;
}