Инне очень нравится цифра 9. Поэтому она попросила Диму написать небольшое число, состоящее из девяток. Но Дима, видимо, что-то перепутал и написал очень большое число a, состоящее из цифр от 1 до 9.
Инна хочет немного поменять число, написанное Димой, чтобы в итоге число содержало как можно больше девяток. За один ход Инна может взять две соседние цифры в числе, сумма которых равна 9, и заменить их на одну цифру 9.
Например, Инна может изменить число 14545181 следующим образом: 14545181 → 1945181 → 194519 → 19919. Также из числа 14545181 описанным способом можно получить число 19991. Число 149591 Инна получать не станет, поскольку можно получить числа 19919 и 19991, а они содержат больше девяток.
Дима — программист, поэтому он хочет узнать сколько различных чисел с максимальным количеством девяток может получить Инна из записанного им числа. Помогите ему с этой нелегкой задачей.
Выходные данные
В единственной строке выведите целое число — ответ на задачу. Гарантируется, что ответ на задачу не превосходит 263 - 1.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
Пояснения к примерам:
В первом примере Инна может получить следующие числа: 369727 → 99727 → 9997, 369727 → 99727 → 9979.
Во втором примере Инна может действовать следующим образом: 123456789987654321 → 12396789987654321 → 1239678998769321.