K. That Time I Got Reincarnated As A String Problem
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Hina has a string $$$s$$$ of lowercase letters and question marks. She wants to fill each question mark with a lowercase letter so that she is left with a string of only lowercase letters. Hina will then count over all permutations of letters in her string, the number of unique strings that can be formed. For instance, the string $$$aab$$$ has $$$6$$$ permutations, $$$[aab, aba, aab, aba, baa, baa]$$$ but only form $$$3$$$ unique strings.

Over all $$$26^{\#\text{ of ?'s}}$$$ ways Hina can fill in the question marks, what is the expected number of unique strings that can be formed?

Input

The first line will contain one integer $$$T$$$, the number of testcases $$$(1 \leq T \leq 500)$$$.

Each following line will contain a string $$$s$$$, the string Hina wants you to find the answer for. $$$s$$$ will only contain lowercase letters or question marks $$$(1 \leq |s| \leq 10^3)$$$.

It is guaranteed that the sum of $$$|s|$$$ over all testcases will not exceed $$$5 \cdot 10^3$$$.

 —

Tests in subtasks will be numbered from $$$1 - 20$$$ with samples ignored.

Tests $$$1-4$$$ will have no strings that contain question marks.

Tests $$$5-6$$$ will have all strings only contain question marks.

Tests $$$7-10$$$ will have the sum of all string lengths not be greater than $$$100$$$.

The remaining testcases have no additional constraints.

Output

For each testcase, output a single integer $$$E$$$, the expected number of permutations over all ways to fill in the question marks modulo $$$10^9 + 7$$$. The expected value can be represented as fraction $$$\frac{x}{y}$$$ and you will output $$$E$$$ where $$$x = E \cdot y \mod 10^9 + 7$$$.

Examples
Input
7
a?b
bestgirl?
rem??
whoisrem???
trust
??
a?
Output
538461548
615691672
165680579
840240076
60
423076928
423076928
Input
2
whatdoyoudoattheendoftheworld?areyoubusy?willyousaveus?
shuumatsunanishitemasuka?isogashiidesuka?sukuttemoratteiidesuka?
Output
954747861
94849604
Note

For the string $$$a?b$$$, when we fill the $$$?$$$ in for $$$a$$$ or $$$b$$$, there are $$$3$$$ permutations but for any letter, there are $$$6$$$. This gives us an expected value of $$$\frac{3 \cdot 2 + 6 \cdot 24}{26} = 538461548 \mod 10^9 +7$$$.

For the string $$$trust$$$, there are no $$$?$$$'s and there can be shown to exist exactly $$$60$$$ unique strings that can be formed from permuting the letters, giving an expected value of $$$60$$$.

Both strings $$$a?$$$ and $$$??$$$ have an expected value of $$$\frac{1 \cdot 1 + 2 \cdot 25}{26} = \frac{51}{26} = 423076928 \mod 10^9 + 7$$$.

For the second sample, you should watch that particular anime <3.

 —

Idea: 3366

Preparation: 3366

Occurrences: Novice 11