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