Processing math: 100%

Задача 3. A + B = C

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:aplusb.in   Ограничение памяти:256 Мб
Выходной файл:aplusb.out  
Максимальный балл:100  

Условие

Часто для пробного тура на различных олимпиадах по информатике предлагается задача «A+B», в которой по заданным целым числам A и B требуется найти их сумму.

При проведении городской олимпиады по информатике председатель жюри решил сам подготовить тесты для такой задачи. Для этого он использовал свою оригинальную методику, которая заключалась в следующем: сначала готовятся предполагаемые правильные ответы, а затем подбираются входные данные, соответствующие этим ответам.

Пусть председатель жюри выбрал число C, запись которого состоит из n десятичных цифр и не начинается с нуля. Теперь он хочет подобрать такие целые положительные числа A и B, чтобы их сумма была равна C, и запись каждого из них также состояла из n десятичных цифр и не начиналась с нуля. В дополнение к этому председатель жюри старается подобрать такие числа A и B, чтобы каждое из них было красивым Красивым в его понимании является число, запись которого не содержит двух одинаковых подряд идущих цифр. Например, число 1272 считается красивым, а число 1227 — нет.

Требуется написать программу, которая для заданного натурального числа C вычисляет количество пар красивых положительных чисел A и B, сумма которых равна C. Поскольку количество пар красивых чисел может быть большим, необходимо вывести остаток от деления этого количества на число 109+7.

Пояснения к примерам

Число 22 можно представить в виде суммы двузначных чисел тремя способами: 10+12, 11+11, 12+10. Способ 11+11 не подходит, поскольку число 11 не является красивым. Следовательно, ответ для числа 22 равен 2.

Число 200 можно представить в виде суммы трехзначных чисел единственным способом: 100+100. Этот способ не подходит, поэтому ответ для числа 200 равен 0.

Число 1000 нельзя представить в виде суммы четырехзначных чисел, поэтому ответ для числа 1000 аналогично равен 0.

Система оценивания

Правильные решения для тестов, в которых 1C999 (1n3), будут оцениваться из 25 баллов.

Правильные решения для тестов, в которых 1C999999 (1n6), будут оцениваться из 50 баллов.

Формат входного файла

Входной файл содержит одно целое положительное число C.

Формат выходного файла

Выходной файл должен содержать одно целое число — остаток от деления количества искомых пар красивых чисел A и B на число 109+7.

Ограничения

Число C не начинается с нуля. Количество цифр в записи числа С не превышает 104.

Примеры тестов

Входной файл (aplusb.in) Выходной файл (aplusb.out)
1
22
2
2
200
0
3
1000
0
4
239
16

0.070s 0.009s 13