回文の拆分

题目背景

问一个数拆成回文数，有多少种拆分方案？

题目描述

给你一个正整数 $n$ 。如果某个不含前导零的正整数 $a$ 在反转其数位顺序后仍然不变，那么我们就称它为回文数。求将 $n$ 表示为回文数之和的方案数。如果两种表达方式中至少有一个回文数的出现次数是不同的，那么这两种表达方式就被认为是不同的。

例如， $5=4+1$ 和 $5=3+1+1$ 被认为是不同的，但 $5=3+1+1$ 和 $5=1+3+1$ 被认为是相同的。

由于答案可能很大，请打印出它对 $10^9+7$ 取模的结果。

输入格式

第一行输入包含一个整数 $t$ ( $1\leq t\leq 10^4$ )，表示测试用例的数量。

每个测试用例都包含一行输入，其中包含一个整数 $n$ ( $1\leq n\leq 4\cdot 10^4$ ) 需要拆分的整数。

输出格式

为每个测试用例打印一个整数，表示拆分的方案数对 $10^9+7$ 取模的结果 。

样例 #1

样例输入 #1

2
5
12

样例输出 #1

7
74

提示

对于$40\%$的数据：$\sum n \le 1000$

对于$100\%$的数据：$t\le10^4,n\le 4\times 10^4$