Задачі
Марафон
Марафон
\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