Westworld
Национална Олимпиада по Информатика 2018
Time Limit: 4s, Memory Limit: 256MiB
Ели с интерес следи сериала Westworld ("Западен Свят"). В новия сезон са показани N пълни години от живота в бъдещето, като всяка сцена представлява случка през някой месец от тези N години. Всеки месец от всяка година е показан точно по веднъж – тоест сезонът има точно 12 * N сцени (по една за всеки месец от показаните N години).

Плот туистът е, че макар и всяка от годините да върви последователно, самите години са размесени една в друга. С други думи, възможно е първо да са показани Януари, Февруари и Март от третата година, после Януари от осмата, после Януари и Февруари от първата, после Април от третата, после Януари до Юни от десетата и т.н.

Ели гледа внимателно сериала и отбелязва за всяка сцена дали има нещо, което показва кое време е. Продуцентите на сериала са се постарали нищо да не издава годините, но пък момичето може да отгатне част от месеците: например, ако се вижда календар, на който е показано кой месец е; или пък е Коледа, от което момичето заключва, че е Декември и т.н.

След като изгледа сериала, Ели осъзна, че е записвала месеците само с първите им букви: 'J' за Януари, 'F' за Февруари, 'M' за Март, 'A' за Април, 'M' за Май, 'J' за Юни, 'J' за Юли, 'A' за Август, 'S' за Септември, 'O' за Октомври, 'N' за Ноември и 'D' за Декември. Месеците, за които Ели не е открила индикатори, е отбелязала с '?'.

Сега Ели се чуди колко възможни "сюжета" може да има сериалът. Под "сюжет" ще разбираме различна последователност от двойки (месец, година), които отговарят на нейните записки. Например, примерът от втория параграф отговаря на "J?MJJ?A??MАМJ", но има и много други възможни "сюжети" – един от тях би бил същия като горния, но последното 'J' да отговаря за Януари на някоя от "незапочнатите" години, вместо Юни от десетата. Сега момичето ви моли да ѝ помогнете, като определите колко възможни сюжета би могъл да има сериалът.
Вход
На първия ред на стандартния вход ще бъде зададен броят години N. На втория ред ще има стринг S с 12 * N символа от азбуката {'J', 'F', 'M', 'A', 'S', 'O', 'N', 'D', '?'} – записките на Ели.
Изход
На стандартния изход изведете едно цяло число – броя различни "сюжети", които би могъл да има сериалът. Тъй като числото може да е много голямо, изведете само остатъка му при деление на 1,000,000,007.
Ограничения
  • 1 ≤ N ≤ 13
  • |S| = 12 * N
Примерен Вход Примерен Изход
2 J??FMAMM?J?JJ???N?A?D??? 72
4 ?J?FMFFMA??JJAA???J????ASM??A?JJMJJA?SOO?DSON?ND 822595037
В първия пример първото 'J' може да е както от първата година, така и от втората (2 варианта). Следват две въпросителни, които могат да са или "JF" или "FJ". Ако са "JF", обаче, се образуват две последователни 'F'-а, които могат да са Февруари месец на която и да е от двете години (3 варианта). Следват Март и Април на някоя от двете години – тъй като и двете са до Февруари, не знаем коя от тях е, така че имаме още 2 варианта. Двете последователни 'M'-та могат да са или (Март, Май) или (Май, Март) – още 2 варианта. Въпросителната след тях е еднозначно определена – тя не може да е нищо друго освен 'A' (Април), тъй като иначе няма как да направим двете последователни 'J'-та по-нататък. Четвъртата въпросителна също не може да е нищо друго освен 'M'. Така двете последователни 'J'-та могат да са или (Юни, Юли) или (Юли, Юни). Забележете, че тук ако са (Юни, Юли) бихме могли да имаме Юли както на едната, така и на другата година - тоест тук имаме нови 3 варианта. Следват три въпросителни, които, обаче, трябва да са "ASO", за да може следващият месец да е Ноември. Въпросителната преди последното 'А' трябва да е 'J', тъй като 'A'-то в този момент не може да е нищо друго освен Август. Тъй като знаем къде е и последният месец от по-напредналата година ('D'-то), то останалите въпросителни са от другата година. Така имаме 2 * 3 * 2 * 2 * 3 = 72 сюжета.

Във втория пример има 5,822,595,072 възможни сюжета. Остатъкът на 5822595072 при деление на 1000000007 е 822595037, което е и отговорът за този тест.
Мрън!