A + B = C
Часто для пробного туру на різних олімпіадах з інформатики пропонується задача "A + B", у якій за заданими цілими числами A та B потрібно знайти їх сумму.
При проведенні міської олімпіади з інформатики голова журі вирішив сам підготувати тести для такої задачі. Для цього він використав свою оригінальну методику, яка полягала у наступному: спочату готуються можливі правильні відповіді, а потім підбираються вхідні дані, які відповідають цим відповідям.
Негаю голова журі вибрав число C, запис якого складається з n десяткових цифр і не починається з нуля. Тепер він хоче підібрати такі цілі додатні числа A та B, щоб їхня сума була рівна C, і запис кожного з них також складався з n десяткових цифр і не починався з нуля. У доповнення до цього голова журі намагається підібрати такі числа A та B, щоб кожне з них було красивим. Красивим у його розумінні є число, запис якого не містить двох однакових цифр, що йдуть підряд. Наприклад, число 1272 вважається красивим, а число 1227 - ні.
Потрібно написати програму, яка для заданого натурального числа C обчислює кількість пар красивих додатніх чисел A та B, сума яких дорівнює C. Оскільки кількість пар красивих чисел може бути великою, необхідно вивести залишок від ділення цієї кількості на число 10^9 + 7.
Вхідні дані
Одне ціле додатне число C. Число C не починається з нуля. Кількість цифр у запису числа С не перевищує 10000.
Вихідні дані
Вивести одне ціле число - залишок від ділення кількості шуканих пар красивих чисел A та B на число 10^9 + 7.
Пояснення до прикладів
Число 22 можна подати у вигляді суми двозначних чисел трьома способами: 10 + 12, 11 + 11, 12 + 10. Спосіб 11 + 11 не підходить, оскільки число 11 не є красивим. Відповідно, відповідь для числа 22 дорівнює 2.
Число 200 можна подати у вигляді суми трьохзначних чисел єдиним способом: 100 + 100. Цей спосіб не підходить, тому відповідь для числа 200 дорівнює 0.
Число 1000 не можна подати у вигляді суми чотирьохзначних чисел, тому відповідь для числа 1000 аналогічно дорівнює 0.