외계 메시지

수년간의 실패 끝에 과학자들은 마침내 우주의 지적 문명과 교신하는 데 성공했고, 외계인의 알파벳이 a와 b 두 글자로만 이루어져 있다는 사실을 알아냈다. 메시지를 수신하기 위해 특수한 수신기가 만들어졌는데, 이 수신기는 a, b 그리고 전송된 문자가 무엇인지 판별하지 못한 경우 특수 문자 ?를 출력한다.

분석 결과 외계인은 모든 메시지를 동일한 두 문자열을 연달아 적은 형태로 전송한다. 예를 들어 "abab"나 "aaaaaa"는 외계인의 메시지가 될 수 있지만, "abba"나 "aaa"는 그럴 수 없다.

과학자들이 만든 장치는 외계인의 잠재적 메시지를 입력받아 위에서 설명한 성질을 고려하지 않고 그 문자열을 읽을 수 있는 모든 방법을 출력한다. 예를 들어 "ab??"라는 문자열을 받으면 장치는 "abaa", "abab", "abba", "abbb"를 출력하는데, 이 중 실제로 외계인의 메시지가 될 수 있는 것은 "abab"뿐이고 나머지 셋은 그럴 수 없다.

장치의 품질을 높이기 위해 과학자들은 장치가 출력한 문자열 중 외계인의 메시지가 될 수 없는 문자열이 몇 개인지 알고 싶어 한다. 이를 도와주자.

첫 번째 줄에는 과학자들이 수신한 메시지에 들어 있는 단어의 수인 자연수 n이 주어진다.

다음 n개 줄 각각에는 메시지에 들어 있는 단어가 주어지며, 이 단어는 a, b, ?로 이루어져 있다. 모든 단어의 길이는 짝수이고, 각 단어에는 ?가 적어도 하나 있다. 모든 단어의 길이 합은 200000을 넘지 않는다. 각 단어를 외계인의 메시지로 해석하는 방법이 적어도 하나 존재한다는 보장은 없다.

n개의 줄을 출력한다. i번째 줄에는 i번째 단어가 올바른 외계인의 메시지가 되지 않도록 ?를 a, b로 바꾸는 방법의 수를 출력한다. 방법의 수가 매우 클 수 있으므로 109+7로 나눈 나머지를 출력해야 한다.