Приветствую. Есть сложная задача!

Для целого положительного числа x определим R(x) как число, равное перевёрнутому x в десятичной записи. Например, R(123) = 321, R(1) = 1, а R(100500) = 5001.

Для данного числа S вычислите количество целых x таких, что 1 ≤ x и x+R(x) ≤ S.

В качестве ответа выведите остаток от деления этого количества на 10^9 + 7.

Всё бы ничего, но вот ограничения на S (0 < S < 10^100 000).

Примеры:
Первый входной тест: 10
Ответ на первый тест: 5
Второй входной тест: 200
Ответ на второй тест: 104
Третий входной тест: 1234
Ответ на третий тест: 715
Четвертый входной тест: 56789
Ответ на четвертый тест: 20951

Первое, что приходит на ум, динамическое программирование, т.е. какие-то рекуррентные соотношения.
Поделитесь своими идеями!

Здравствуйте, Rimdalf!
С математической точки зрения, как смог, упростил вашу задачу. Дальше мне кажется, что можно только перебором с помощью программирования. Но на программирование уже ни сил, ни времени нет.

Здравствуйте, SergeiB.
Огромное спасибо!
В разборе на S = 200 есть ошибки: там не может быть 101, 121, 141, 161, 181.
Т.к. Например, 141 + реверс(141) = 282
99 чисел - это да, но потом 100, 110, 120, 130, 140

Здравствуйте, Rimdalf!
Нет, там ошибки нет. Просто в этом разборе из-за его простоты я указал значения суммы x+R(x) (первое, что пришло в голову), а в других разборах для удобства указывал значения чисел х, вот вы и запутались.
100+001=101; 110+011=121; 120+021=141; 130+031=161; 140+041=181

Здравствуйте всем, кого заинтересовала задача про числа!
С Новым годом и Рождеством!
На праздниках появилось время, и я решил проверить, насколько полезна идея, предложенная мной выше.
В общем попробовал написать программу на основе этой идеи. Добавил то, что получилось в предыдущий файл.
Вроде бы программа считает правильно и достаточно быстро, но для больших чисел S, я её не проверял.
Технические возможности мне не интересны. Файл Word добавил потому, что из него, мне кажется, проще скопировать программу, если появится такое желание.