시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 12 | 7 | 7 | 58.333% |
После многих лет безуспешных попыток ученые наконец-то смогли установить связь с разумной цивилизацией в космосе и выяснили, что алфавит инопланетян состоит всего из двух букв: a
и b
. Для приема сообщений был сконструирован специальный приемник, который выдает символы a
, b
, а также специальный символ ?
, если разобрать, какой символ был передан, не удалось.
Анализ показал, что инопланетяне передают все свои сообщения в виде двух одинаковых записанных подряд строк. Например, строки «abab
» или «aaaaaa
» могут быть сообщениями инопланетян, а «abba
» или «aaa
» — нет.
Прибор, сконструированный учеными, получив на вход потенциальное сообщение инопланетян, выдает все возможные способы прочитать строку без учета описанного выше свойства. Например, получив строку «ab??
» прибор выдает строки «abaa
», «abab
», «abba
» и «abbb
», из них на самом деле только строка «abab
» может быть сообщением от инопланетян, а остальные три не могут.
Для улучшения качества прибора ученые хотят узнать, сколько строк из тех, которые выведены прибором, не могут быть сообщением инопланетян. Помогите им это сделать.
В первой строке содержится натуральное число n — число слов в сообщении, полученного учеными.
В каждой из следующих n строк содержится слово из сообщения, состоящее из символов a
, b
и ?
. Гарантируется, что все слова имеет четную длину, а также, что в каждом слове есть хотя бы один ?
. Суммарная длина всех слов не превышает 200000. Не гарантируется, что есть хотя бы один способ расшифровать каждое слово как сообщение инопланетян.
Выведите n строк. В i-ой строке выведите число способов заменить ?
на буквы a
, b
так, чтобы i-е слово не было корректным сообщением инопланетян. Так как число способов может быть очень большим, необходимо выводить его по модулю 109+7.
3 ab?b baa? abb???
1 2 7