Задачи
Марафон
Марафон
\includegraphics{https://static.e-olymp.com/content/15/15803ae578e5bf355f376528f8d35472c71f5e98.jpg}
Наблюдая за соревнованиями по марафонскому бегу, которые проходили прямо на улицах Лондона, Вася делал какие-то свои интересные заметки… Он отмечал каждую пару пробежавших мимо него спортсменов цифрой \textbf{2}, если номер второго спортсмена был больше номера первого, и цифрой \textbf{1}, если наоборот. Правда иногда Васю отвлекали, и он мог и забыть предыдущий номер… В этом случае (если Вася забывал номер предыдущего спортсмена), Вася помечал этот факт в своей записной книжке символом '\textbf{?}'.
Например, если спортсмены пробежали перед Васей в порядке \{\textbf{3},\textbf{1},\textbf{2},\textbf{7},\textbf{4},\textbf{6},\textbf{5}\}, то у Васи в записной книжке появлялась запись: "\textbf{122121}".
Ваша задача заключается в следующем: за заданной строкой из блокнотика Васи посчитать количество возможных вариантов порядков пробега спортсменов перед ним. Известно, что номера спортсменам-марафонцам на олимпиаде \textbf{2012 }выдавались подряд, начиная с \textbf{1}, и ни один из стартовавших спортсменов не сошёл с дистанции раньше, чем пробежал перед Васей.
\InputFile
Каждый тест сдержится в отдельной строке и состоит из набора от \textbf{1} до \textbf{1000} символов, содержащих только цифры '\textbf{1}', '\textbf{2}' или символ '\textbf{?}'. Гарантируется, что все входные данные корректны и не содержат начальных и концевых пробелов. Входные данные продолжаются до конца файла.
\OutputFile
Для каждого теста в отдельной строке выведите количество перестановок номеров спортсменов, удовлетворяющих заданной входной строке Васи. Так как результат может быть очень большим, ответ необходимо вывести по модулю \textbf{20122013}.
Входные данные #1
22 21 12 11 ?1 ??
Выходные данные #1
1 2 2 1 3 6