PROGRAMMING:The Alphabet Sticker
When we were kids, we used to play with some stickers where these stickers contain some (but not
necessarily all) lower case English alphabet letters.
Each sticker contains some letters arranged in a single row, where all occurrences of the same letter are
adjacent to each other. A sticker can be represented as a string of characters, for example the following
are valid stickers’ representations: “aabcc”, “ccccab” and “mmaw”. And the following are not valid (because
not all occurrences of the same letter are adjacent to each other): “abacc”, “cccabc” and “mawm”.
Now we found some stickers with some missing letters, but we are sure that all missing letters belong to
the visible letters set (that is, for every missing letter, there is at least one visible letter that matches
the missing one). In this problem a question mark letter represents a missing letter. Given some stickers’
representations with zero or more missing letters, your task is to count the number of possible original
configurations for each sticker.
For example, this sticker “aa?? bb” with missing letters could have been one of the following original stickers
“aaaabb”, “aaabbb” or “aabbbb”. But it could not have been any of the following original stickers “aababb”
(it is invalid sticker) and “aaccbb” (because the letter ‘c’ did not appear in the given configuration).
Summary of the theme:
Here's a string with some '?' Is unknown, and these '?' Only existing characters can define legal strings for all
The same letters are arranged together, for example: AABB, aabbcdd
How many legal results are there for a given string? The final result is modulo 1e9 + 7
###Input format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer
T, the number of test cases (1 ≤ T ≤ 100). Followed by the test cases, each test case is described in one
line which contains a non-empty string which consists of up to 10,000 letters, each letter is either a lower
case English letter (from ‘a’ to ‘z’) or a question mark (‘?’). This string represents a sticker configuration
which contains zero or more question marks, it will also contain at least one letter which is not a question
mark and there will be at least one valid original configuration for it.
###Output format:
For each test case, print a single line which contains a single integer representing the number of possible
original configurations for the sticker, since the result may be very large, print it modulo 1,000,000,007
(109 + 7).
###Input example:
Here is a set of inputs. For example:
```in
four
aa?? bb
aaccbb
? a?
a?? a
```
###Output example:
The corresponding output is given here. For example:
```out
three
one
one
one
```
answer：If there is no answer, please comment
necessarily all) lower case English alphabet letters.
Each sticker contains some letters arranged in a single row, where all occurrences of the same letter are
adjacent to each other. A sticker can be represented as a string of characters, for example the following
are valid stickers’ representations: “aabcc”, “ccccab” and “mmaw”. And the following are not valid (because
not all occurrences of the same letter are adjacent to each other): “abacc”, “cccabc” and “mawm”.
Now we found some stickers with some missing letters, but we are sure that all missing letters belong to
the visible letters set (that is, for every missing letter, there is at least one visible letter that matches
the missing one). In this problem a question mark letter represents a missing letter. Given some stickers’
representations with zero or more missing letters, your task is to count the number of possible original
configurations for each sticker.
For example, this sticker “aa?? bb” with missing letters could have been one of the following original stickers
“aaaabb”, “aaabbb” or “aabbbb”. But it could not have been any of the following original stickers “aababb”
(it is invalid sticker) and “aaccbb” (because the letter ‘c’ did not appear in the given configuration).
Summary of the theme:
Here's a string with some '?' Is unknown, and these '?' Only existing characters can define legal strings for all
The same letters are arranged together, for example: AABB, aabbcdd
How many legal results are there for a given string? The final result is modulo 1e9 + 7
###Input format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer
T, the number of test cases (1 ≤ T ≤ 100). Followed by the test cases, each test case is described in one
line which contains a non-empty string which consists of up to 10,000 letters, each letter is either a lower
case English letter (from ‘a’ to ‘z’) or a question mark (‘?’). This string represents a sticker configuration
which contains zero or more question marks, it will also contain at least one letter which is not a question
mark and there will be at least one valid original configuration for it.
###Output format:
For each test case, print a single line which contains a single integer representing the number of possible
original configurations for the sticker, since the result may be very large, print it modulo 1,000,000,007
(109 + 7).
###Input example:
Here is a set of inputs. For example:
```in
four
aa?? bb
aaccbb
? a?
a?? a
```
###Output example:
The corresponding output is given here. For example:
```out
three
one
one
one
```
answer：If there is no answer, please comment