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

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

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

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

Лука - торговец картинами. У него есть N клиентов, каждому из которых он продает произведения искусства. Каждый клиент может купить либо цветные картины, либо черно-белые, но не те и другие вместе. При этом клиент под номером i готов купить не более a _i цветных картин и не более b _i черно-белых картин. При этом каждый клиент хочет купить хотя бы одну картину.

У Луки практически неограниченный запас картин, поэтому запросы клиентов не являются для него проблемой. Однако, Лука не любит продавать черно-белые картины, и если окажется, что меньше, чем C людей купили цветные картины, он очень огорчится.

В силу нестабильной экономической ситуации в стране клиенты постоянно изменяют свои запросы, иными словами количество цветных и черно-белых картин, которые они готовы купить. Из-за этого Лука постоянно задается вопросом: "Сколько у меня есть вариантов, как продать клиентам картины, чтобы хотя бы C человек купили цветные картины?". Помогите Луке и защитите его от излишнего беспокойства.