The Alphabet Sticker

Interview

Time limit1sMemory limit128 MB

Summary

Count completions of a sticker pattern where each question mark becomes a visible letter and every letter forms one contiguous block.

Level: Medium5 of 10
Topics: Combinatorics, String
Solved: No attempts yet

Problem

When we were kids we played with stickers that had lowercase English letters printed on them. A sticker carries some of the letters, not necessarily all 26.

The letters on a sticker sit in a single row, and all occurrences of the same letter are next to each other, so a sticker is a string. aabcc, ccccab and mmaw are valid stickers. abacc, cccabc and mawm are not, because the same letter shows up in two separate places.

We found stickers with some letters worn off. Every worn-off letter is one of the letters still visible on the same sticker: for each missing letter, at least one matching letter is still readable. A question mark ? marks a missing letter. Given a sticker with zero or more question marks, count the original stickers it could have come from.

For example, aa??bb was originally aaaabb, aaabbb or aabbbb. It cannot have been aababb, which is not a valid sticker, and it cannot have been aaccbb, because c is not visible in the given sticker.

Input

The first line has the number of test cases $T$ . ( $1 \le T \le 100$ )

Each test case is one line holding a string whose length is between 1 and 10,000. Each character is a lowercase English letter (a to z) or a question mark (?). A string may hold no question marks or many. Every string holds at least one letter that is not a question mark, and at least one valid original sticker exists for it.

Output

For each test case, print one line with the number of possible original stickers modulo 1,000,000,007 ( $10^9 + 7$ ).

Examples1

Example 1
Input
```
4
aa??bb
aaccbb
?a?
a??a
```
Expected output
```
3
1
1
1
```