B. Инна и девять
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Инне очень нравится цифра 9. Поэтому она попросила Диму написать небольшое число, состоящее из девяток. Но Дима, видимо, что-то перепутал и написал очень большое число a, состоящее из цифр от 1 до 9.

Инна хочет немного поменять число, написанное Димой, чтобы в итоге число содержало как можно больше девяток. За один ход Инна может взять две соседние цифры в числе, сумма которых равна 9, и заменить их на одну цифру 9.

Например, Инна может изменить число 14545181 следующим образом: 14545181 → 1945181 → 194519 → 19919. Также из числа 14545181 описанным способом можно получить число 19991. Число 149591 Инна получать не станет, поскольку можно получить числа 19919 и 19991, а они содержат больше девяток.

Дима — программист, поэтому он хочет узнать сколько различных чисел с максимальным количеством девяток может получить Инна из записанного им числа. Помогите ему с этой нелегкой задачей.

Входные данные

Первая строка входных данных содержит целое число a (1 ≤ a ≤ 10100000). Число a не содержит в своей записи нулей.

Выходные данные

В единственной строке выведите целое число — ответ на задачу. Гарантируется, что ответ на задачу не превосходит 263 - 1.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
369727
Выходные данные
2
Входные данные
123456789987654321
Выходные данные
1
Входные данные
1
Выходные данные
1
Примечание

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

В первом примере Инна может получить следующие числа: 369727 → 99727 → 9997, 369727 → 99727 → 9979.

Во втором примере Инна может действовать следующим образом: 123456789987654321 → 12396789987654321 → 1239678998769321.