Часто для пробного туру на різних олімпіадах з інформатики пропонується задача "A + B", у якій за заданими цілими числами A та B потрібно знайти їх сумму.

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

Негаю голова журі вибрав число C, запис якого складається з n десяткових цифр і не починається з нуля. Тепер він хоче підібрати такі цілі додатні числа A та B, щоб їхня сума була рівна C, і запис кожного з них також складався з n десяткових цифр і не починався з нуля. У доповнення до цього голова журі намагається підібрати такі числа A та B, щоб кожне з них було красивим. Красивим у його розумінні є число, запис якого не містить двох однакових цифр, що йдуть підряд. Наприклад, число 1272 вважається красивим, а число 1227 - ні.

Потрібно написати програму, яка для заданого натурального числа C обчислює кількість пар красивих додатніх чисел A та B, сума яких дорівнює C. Оскільки кількість пар красивих чисел може бути великою, необхідно вивести залишок від ділення цієї кількості на число 109 + 7.

Вхідні дані

Одне ціле додатне число C. Число C не починається з нуля. Кількість цифр у запису числа С не перевищує 10000.

Вихідні дані

Вивести одне ціле число - залишок від ділення кількості шуканих пар красивих чисел A та B на число 109 + 7.

Пояснення до прикладів

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

Число 200 можна подати у вигляді суми трьохзначних чисел єдиним способом: 100 + 100. Цей спосіб не підходить, тому відповідь для числа 200 дорівнює 0.

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