Marafon#3612
Londonda küçələrdə keçirilən marafon qaçış yarışlarını izləyərkən, Vasya maraqlı qeydlər aparırdı. O, yanından keçən hər bir idmançı cütlüyünü qeyd edirdi: əgər ikinci idmançının nömrəsi birincinin nömrəsindən böyük idisə, 2 rəqəmi ilə, əks halda 1 rəqəmi ilə işarələyirdi. Bəzən Vasya diqqətini yayındırır və əvvəlki nömrəni unuda bilirdi. Belə hallarda (əgər Vasya əvvəlki idmançının nömrəsini unudurdusa), bu faktı dəftərində '?' simvolu ilə qeyd edirdi.
Məsələn, əgər idmançılar Vasya qarşısından {3,1,2,7,4,6,5} ardıcıllığı ilə keçmiş olsaydılar, Vasyanın dəftərində belə bir qeyd yaranardı: "122121".
Sizin vəzifəniz belədir: Vasyanın dəftərindəki verilmiş sıra əsasında idmançıların onun qarşısından keçmə ardıcıllığının mümkün variantlarının sayını hesablamaq. Məlumdur ki, 2012-ci il Olimpiadasında marafonçulara nömrələr ardıcıl olaraq 1-dən başlayaraq verilmişdir və heç bir idmançı Vasya qarşısından keçməmişdən əvvəl yarışı tərk etməmişdir.
Hər bir test ayrıca bir sətirdə yerləşir və yalnız '1', '2' rəqəmlərindən və ya '?' simvolundan ibarət olan 1 ilə 1000 arasında simvollardan ibarət dəstdən ibarətdir. Bütün giriş məlumatlarının düzgün olduğu və başlanğıc və son boşluqların olmadığı təmin edilir. Giriş məlumatları faylın sonuna qədər davam edir.
Hər bir test üçün ayrıca bir sətirdə Vasyanın verilmiş giriş sətirinə uyğun gələn idmançı nömrələrinin permutasiyalarının sayını çıxarın. Nəticə çox böyük ola biləcəyi üçün cavabı 20122013 modulu ilə çıxarmaq lazımdır.
Nümunə 1