Марафон
Наблюдая за соревнованиями по марафонскому бегу, которые проходили прямо на улицах Лондона, Вася делал какие-то свои интересные заметки… Он отмечал каждую пару пробежавших мимо него спортсменов цифрой 2, если номер второго спортсмена был больше номера первого, и цифрой 1, если наоборот. Правда иногда Васю отвлекали, и он мог и забыть предыдущий номер… В этом случае (если Вася забывал номер предыдущего спортсмена), Вася помечал этот факт в своей записной книжке символом '?'.
Например, если спортсмены пробежали перед Васей в порядке {3,1,2,7,4,6,5}, то у Васи в записной книжке появлялась запись: "122121".
Ваша задача заключается в следующем: за заданной строкой из блокнотика Васи посчитать количество возможных вариантов порядков пробега спортсменов перед ним. Известно, что номера спортсменам-марафонцам на олимпиаде 2012 выдавались подряд, начиная с 1, и ни один из стартовавших спортсменов не сошёл с дистанции раньше, чем пробежал перед Васей.
Входные данные
Каждый тест сдержится в отдельной строке и состоит из набора от 1 до 1000 символов, содержащих только цифры '1', '2' или символ '?'. Гарантируется, что все входные данные корректны и не содержат начальных и концевых пробелов. Входные данные продолжаются до конца файла.
Выходные данные
Для каждого теста в отдельной строке выведите количество перестановок номеров спортсменов, удовлетворяющих заданной входной строке Васи. Так как результат может быть очень большим, ответ необходимо вывести по модулю 20122013.