Дневник в цифрах: сколько расшифровок?

В школьном дневнике кто-то спрятал текст: каждую букву A..Z заменили её номером в алфавите (A = 1, B = 2, ..., Z = 26) и просто приписали все числа подряд, без разделителей.

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

Если некоторую расшифровку невозможно получить (например, из-за одиночного нуля или числа больше 26), то она не считается.

Ответ выведи по модулю 1 000 000 007.

Формат ввода

Одна строка s — непустая строка из цифр (0–9).

Формат вывода

Одно целое число — количество возможных расшифровок строки s по модулю 1 000 000 007.

Ограничения

• 1 ≤ |s| ≤ 200000

Пример

Ввод:

226

Вывод:

3