Задача №114970. Особенные числа
Число \(a\) называется палиндромом, если оно читается одинаково справа налево и слева направо. Число \(a\) называется особенным, если оно палиндром и число \(11 \cdot a\) тоже палиндром. Вам дано \(n\) запросов, в каждом из них вы должны найти количество особенных чисел от \(1\) до \(a_i\). Так как ответ может быть большим, найдите результат по модулю \(10^9 + 7\).
В первой строке вводится единственное целое число \(n\) (\(1 \leq n \leq 1000\)) — количество запросов.
В следующих \(n\) строках вводится по одному числу \(a_i\) (\(1 \leq a_i \leq 10^{5000}\)) — \(i\)-й запрос.
Для каждого запроса в отдельной строке выведите единственное целое число — количество особенных чисел от \(1\) до \(a_i\) по модулю \(10^9 + 7\).
В примере при \(a_i = 10\) особенные числа меньшие 10 это: 1, 2, 3, 4, 5, 6, 7, 8, 9.
При \(a_i = 45\) особенные числа это: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44.
Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||
| Группа | Баллы | \(a_i\) | \(n\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 15 | \(a_i \le 70\,000\) | \(n \le 100\) | 0 | |
| 2 | 9 | \(a_i \le 2 \cdot 10^{6}\) | – | 0, 1 | |
| 3 | 14 | \(a_i \le 10^{8}\) | \(n \le 100\) | 0, 1 | |
| 4 | 11 | \(a_i \le 10^{11}\) | – | 0–3 | |
| 5 | 25 | \(a_i \le 10^{18}\) | – | 0–4 | |
| 6 | 26 | – | – | 0–5 | Offline-проверка |
5 10 45 79 113 467
9 13 13 15 43