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

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

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

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