小时候，我们经常玩贴纸，这些贴纸上包含一些（但不一定是全部）小写英文字母。

每张贴纸上的字母排成一行，且相同字母的所有出现位置都是相邻的。贴纸可以用一个字符串来表示，例如，以下是合法的贴纸表示：“aabcc”、“ccccab” 和 “mmaw”。而以下是不合法的（因为相同字母的出现位置不全相邻）：“abacc”、“cccabc” 和 “mawm”。

现在我们发现了一些带有缺失字母的贴纸，但我们确定所有缺失的字母都属于已出现的字母集合（即，对于每个缺失的字母，至少有一个与之相同的可见字母）。在本题中，问号字符代表缺失的字母。给定一些带有零个或多个缺失字母的贴纸表示，你的任务是计算每张贴纸可能的原始配置数量。

例如，带有缺失字母的贴纸 “aa??bb” 可能是以下原始贴纸之一：“aaaabb”、“aaabbb” 或 “aabbbb”。但它不可能是以下原始贴纸：“aababb”（因为它是非法贴纸）和 “aaccbb”（因为字母 ‘c’ 没有出现在给定的配置中）。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量 ($1 \le T \le 100$)。接下来是各个测试用例，每个测试用例由一行描述，包含一个非空字符串，长度不超过 10,000，每个字符要么是小写英文字母（从 ‘a’ 到 ‘z’），要么是问号（‘?’）。该字符串表示一个包含零个或多个问号的贴纸配置，它至少包含一个非问号字符，并且保证至少存在一种合法的原始配置。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示该贴纸可能的原始配置数量。由于结果可能非常大，请输出其对 $1,000,000,007$ ($10^9 + 7$) 取模的结果。

样例

输入 1

4
aa??bb
aaccbb
?a?
a??a

输出 1

3
1
1
1