这道题非常板，如你所见，大概思路是打表回文数加上完全背包求方案数，但是需要注意取余问题。
从英文题面上（题目翻译没有给出数据范围）可以看到 \(1 \leq n \leq 4 \cdot 10 ^ {4}\)，所以只要用完全背包来预处理这一范围即可。如果你还是不懂，可以去搜完全背包字样并学习该算法。
一些题解中的写法并不显然，所以我将代码写的更加贴近板子（虽然老师写的不显然）。
#include <iostream>
#include <vector>
namespace io{
template <typename T> inline void read(T& x){x = 0; bool f = false; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-') f = !f; ch = getchar();}while(ch >= '0' && ch <= '9'){x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();} x = (f ? -x : x); return;}
template <typename T, typename... Args> inline void read(T& x, Args&...x_){read(x), read(x_...);}
template <typename T> inline void put(T x){if(x < 0) putchar('-'), x = -x; if(x > 9) put(x / 10); putchar(x % 10 + '0'); return ;}
template <typename T> inline void write(T x){put(x);}
template <typename T, typename... Args> inline void write(T x, Args...x_){write(x), write(x_...);}
inline void newb(){putchar(' ');}
inline void newl(){puts("");}
}
namespace code{
int t, dp[1000001];
std::vector <int> vec;
const int mod = 1e9 + 7;
bool palin(std::string s){
int len = s.length();
for(int i = 0; i < len; i++) if(s[i] != s[len - i - 1]) return false;
return true;
}
int main(){
for(int i = 1; i <= 40000; i++) if(palin(std::to_string(i)) == true) vec.push_back(i);
dp[0] = 1;
for(int i = 0; i < vec.size(); i++) for(int j = vec[i]; j <= 40000; j++) dp[j] = (dp[j] + dp[j - vec[i]]) % mod;
io::read(t);
while(t--){
int x;
io::read(x);
io::write(dp[x]);
puts("");
}
return 0;
}
}
int main(){
code::main();
return 0;
}