Марафон#3612
Спостерігаючи за змаганнями з марафонського бігу, які проходили прямо на вулицях Лондона, Вася робив якісь свої цікаві помітки… Він відмічав кожну пару спортсменів, які пробігали мимо нього, цифрою , якщо номер другого спортсмена був більшим номера першого, і цифрою , якщо навпаки. Правда іноді Васю відволікали, і він міг і забути попередній номер… У цьому випадку (якщо Вася забував номер попереднього спортсмена), Вася відмічав цей факт у своєму блокнотику символом '?'.
Наприклад, якщо спортсмени пробігли перед Васею у порядку \{3,1,2,7,4,6,5\}, то у блокнотику Васі з'являвся запис: "122121".
Ваша задача полягає у наступному: за заданим рядком з блокнотику Васі порахувати кількість можливих варіантів вказаного порядку пробігу спортсменів перед ним. Відомо, що номери спортсменам-марафонцям на олімпіаді видавали підряд, починаючи з , і жоден із спортсменів не зійшов з дистанції раніше, ніж пробіг перед Васею.
Кожен тест міститься у окремому рядку і складається з набору від до символів, який містить лише цифри '1', '2' або символ '?'. Гарантується, що усі вхідні дані коректні і не містять початкових та кінцевих пропусків. Вхідні дані продовжуються до кінця файлу.
Для кожного тесту у окремому рядку виведіть кількість перестановок номерів спортсменів, які задовольняють заданому вхідному рядку Васі. Так як результат може бути дуже великим, відповідь потрібно вивести по модулю .
Приклад 1