Alien Message

After many years of failed attempts, scientists have finally managed to establish contact with an intelligent civilization in space, and they learned that the alien alphabet consists of just two letters: a and b. A special receiver was built to receive messages, and it outputs the characters a, b, as well as a special character ? when it cannot determine which character was transmitted.

Analysis showed that the aliens transmit all their messages as two identical strings written one after the other. For example, the strings "abab" or "aaaaaa" can be messages from the aliens, while "abba" or "aaa" cannot.

The device the scientists built takes a potential alien message as input and outputs all possible ways to read the string without taking the property described above into account. For example, given the string "ab??", the device outputs the strings "abaa", "abab", "abba", and "abbb", of which only the string "abab" can actually be a message from the aliens, while the other three cannot.

To improve the quality of the device, the scientists want to know how many of the strings the device outputs cannot be messages from the aliens. Help them do this.

The first line contains a natural number n, the number of words in the message the scientists received.

Each of the following n lines contains a word from the message, consisting of the characters a, b, and ?. It is guaranteed that all words have even length, and that each word contains at least one ?. The total length of all words does not exceed 200000. It is not guaranteed that there is at least one way to decode each word as an alien message.

Output n lines. On the i-th line, output the number of ways to replace ? with the letters a, b so that the i-th word is not a valid alien message. Since the number of ways can be very large, output it modulo 109+7.