22124번 - Сообщение 다국어

문제

После многих лет безуспешных попыток ученые наконец-то смогли установить связь с разумной цивилизацией в космосе и выяснили, что алфавит инопланетян состоит всего из двух букв: a и b. Для приема сообщений был сконструирован специальный приемник, который выдает символы a, b, а также специальный символ ?, если разобрать, какой символ был передан, не удалось.

Анализ показал, что инопланетяне передают все свои сообщения в виде двух одинаковых записанных подряд строк. Например, строки «abab» или «aaaaaa» могут быть сообщениями инопланетян, а «abba» или «aaa» — нет.

Прибор, сконструированный учеными, получив на вход потенциальное сообщение инопланетян, выдает все возможные способы прочитать строку без учета описанного выше свойства. Например, получив строку «ab??» прибор выдает строки «abaa», «abab», «abba» и «abbb», из них на самом деле только строка «abab» может быть сообщением от инопланетян, а остальные три не могут.

Для улучшения качества прибора ученые хотят узнать, сколько строк из тех, которые выведены прибором, не могут быть сообщением инопланетян. Помогите им это сделать.

입력

В первой строке содержится натуральное число n — число слов в сообщении, полученного учеными.

В каждой из следующих n строк содержится слово из сообщения, состоящее из символов a, b и ?. Гарантируется, что все слова имеет четную длину, а также, что в каждом слове есть хотя бы один ?. Суммарная длина всех слов не превышает 200000. Не гарантируется, что есть хотя бы один способ расшифровать каждое слово как сообщение инопланетян.

출력

Выведите n строк. В i-ой строке выведите число способов заменить ? на буквы a, b так, чтобы i-е слово не было корректным сообщением инопланетян. Так как число способов может быть очень большим, необходимо выводить его по модулю 10⁹+7.

제한

힌트