lighter   3년 전

수 년 간의 시도 끝에, 과학자들은 마침내 우주의 지능적인 문명과 교신을 할 수 있게 되었고, 외계 문자가 'a'와 'b', 단 두 개의 문자로 구성되어 있다는 것을 발견했습니다. 과학자들은 어떤 문자가 전송되었는지 분석할 수 없는 경우 '?'로 해석하도록 하는 특수 수신기로 교신을 합니다.

과학자들의 분석 결과, 외계인들은 같은 메시지를 연속적으로 두 번 전송함을 알아냈습니다. 예를 들어, "abab" 또는 "aaaaaa" 문자열은 외계인의 메시지일 수 있지만, "abba" 또는 "aaa"는 그렇지 않습니다.

과학자들에 의해 설계된 이 특수 수신기는, 외계인들로부터 메시지를 받아 해석할 수 있는 모든 경우를 보여줍니다. 예를 들어, 문자열 "ab??"가 주어지면, 이 장치는 문자열 "abaa", "abab", "abba", "abbb"를 출력하는데, 이 중 문자열 "abab"만이 외계인의 메시지가 될 수 있습니다.

이 장치의 품질을 향상 시키기 위해, 과학자들은 이 장치에 의해 출력 된 문자열 중 얼마나 많은 문자열이 외계인의 메시지가 될 수 없는지 알고 싶어합니다.

입력

첫 번째 줄에는 과학자들이 받은 메시지 수인 자연수 n이 포함되어 있습니다.

다음 n줄 각각은 'a', 'b', '?' 문자로 구성된 문자열이 주어집니다. 문자열에는 적어도 하나의 '?' 문자가 있다는 것을 보증합니다. 모든 메시지의 총 길이는 200000을 초과하지 않습니다. 각각의 문자열을 외계인의 메시지로 해독할 수 있는 방법이 없을 수도 있습니다.

출력

각 케이스마다 '?'문자를 'a'또는 'b'문자로 대체함으로써 외계인의 메시지로 해독할 수 없는 경우의 수를 출력합니다. 방법의 수가 매우 많을 수 있기 때문에 모듈로 10^9+7를 취해주세요.

댓글을 작성하려면 로그인해야 합니다.