A + B = C
(Время: 2 сек. Память: 16 Мб Сложность: 47%)
Часто для пробного тура на различных олимпиадах по информатике предлагается задача «A + B», в которой по заданным целым числам A и B требуется найти их сумму.
При проведении городской олимпиады по информатике председатель жюри решил сам подготовить тесты для такой задачи. Для этого он использовал свою оригинальную методику, которая заключалась в следующем: сначала готовятся предполагаемые правильные ответы, а затем подбираются входные данные, соответствующие этим ответам.
Пусть председатель жюри выбрал число C, запись которого состоит из n десятичных цифр и не начинается с нуля. Теперь он хочет подобрать такие целые положительные числа A и B, чтобы их сумма была равна C, и запись каждого из них также состояла из n десятичных цифр и не начиналась с нуля. В дополнение к этому председатель жюри старается подобрать такие числа A и B, чтобы каждое из них было красивым. Красивым в его понимании является число, запись которого не содержит двух одинаковых подряд идущих цифр. Например, число 1272 считается красивым, а число 1227 — нет.
Требуется написать программу, которая для заданного натурального числа C вычисляет количество пар красивых положительных чисел A и B, сумма которых равна C. Поскольку количество пар красивых чисел может быть большим, необходимо вывести остаток от деления этого количества на число 109+7.
Входные данные
Входной файл INPUT.TXT содержит одно целое положительное число C. Число C не начинается с нуля. Количество цифр в записи числа С не превышает 10 000.
Выходные данные
В выходной файл OUTPUT.TXT должен содержать одно целое число — остаток от деления количества искомых пар красивых чисел A и B на число 109+7.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 22 | 2 |
| 2 | 200 | 0 |
| 3 | 1000 | 0 |
| 4 | 239 | 16 |
Пояснения к примерам
Число 22 можно представить в виде суммы двузначных чисел тремя способами: 10 + 12, 11 + 11, 12 + 10. Способ 11 + 11 не подходит, поскольку число 11 не является красивым. Следовательно, ответ для числа 22 равен 2.
Число 200 можно представить в виде суммы трехзначных чисел единственным способом: 100 + 100. Этот способ не подходит, поэтому ответ для числа 200 равен 0.
Число 1000 нельзя представить в виде суммы четырехзначных чисел, поэтому ответ для числа 1000 аналогично равен 0.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
