C. Палиндромный базис
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано положительное целое число $$$n$$$. Назовём некоторое положительное целое число $$$a$$$ без лидирующих нулей палиндромным, если оно остаётся таким же после переворота порядка его цифр. Найдите количество способов представить $$$n$$$ как сумму положительных палиндромных чисел. Два способа считаются различными, если количества вхождений хотя бы одного палиндромного числа в них различаются. Например, $$$5=4+1$$$ и $$$5=3+1+1$$$ считаются различными, но $$$5=3+1+1$$$ и $$$5=1+3+1$$$ считаются одинаковыми.

Формально, вам нужно найти количество различных мультимножеств положительных палиндромных чисел, сумма которых равна $$$n$$$.

Поскольку ответ может быть очень большим, выведите его по модулю $$$10^9+7$$$.

Входные данные

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1\leq t\leq 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных содержит единственное целое число $$$n$$$ ($$$1\leq n\leq 4\cdot 10^4$$$) — требуемую сумму палиндромных чисел.

Выходные данные

Для каждого набора входных данных выведите единственное целое число, обозначающее требуемый ответ по модулю $$$10^9+7$$$.

Пример
Входные данные
2
5
12
Выходные данные
7
74
Примечание

Для первого набора входных данных существует $$$7$$$ способов представить $$$5$$$ как сумму положительных палиндромных чисел:

  • $$$5=1+1+1+1+1$$$
  • $$$5=1+1+1+2$$$
  • $$$5=1+2+2$$$
  • $$$5=1+1+3$$$
  • $$$5=2+3$$$
  • $$$5=1+4$$$
  • $$$5=5$$$

Во втором наборе входных данных существует всего $$$77$$$ способов представить $$$12$$$ как сумму положительных целых чисел, но среди них представления $$$12=2+10$$$, $$$12=1+1+10$$$ и $$$12=12$$$ не являются корректными представлениями $$$12$$$ как сумму положительных палиндромных чисел, поскольку $$$10$$$ и $$$12$$$ не являются палиндромными числами. Таким образом, существует $$$74$$$ способа представить $$$12$$$ как сумму положительных палиндромных чисел.