Вам дано положительное целое число \(n\). Назовём некоторое положительное целое число \(a\) без лидирующих нулей палиндромным, если оно остаётся таким же после переворота порядка его цифр. Найдите количество способов представить \(n\) как сумму положительных палиндромных чисел. Два способа считаются различными, если количества вхождений хотя бы одного палиндромного числа в них различаются. Например, \(5=4+1\) и \(5=3+1+1\) считаются различными, но \(5=3+1+1\) и \(5=1+3+1\) считаются одинаковыми.
Формально, вам нужно найти количество различных мультимножеств положительных палиндромных чисел, сумма которых равна \(n\).
Поскольку ответ может быть очень большим, выведите его по модулю \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите единственное целое число, обозначающее требуемый ответ по модулю \(10^9+7\).
Примечание
Для первого набора входных данных существует \(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\) как сумму положительных палиндромных чисел.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
12
|
7
74
|