Description

根据一种流行的说法，计算机程序员喝很多咖啡，并且只知道几个单词。一个典型程序员的词汇量只有三个单词。此外，他很少知道如何拼写它们。为了帮助程序员纠正拼写错误，我们出版了一本名为《每个典型程序员应该知道的三个单词词典》的书。

你得到了一本书的副本，但不久之后，你把咖啡洒在了上面。

现在，你无法阅读其中的一些字符。幸运的是，这三个单词在字典中是不同的，并按字典顺序排列。在你尝试利用这一事实来恢复缺失的字符之前，你想知道有多少种不同的方法可以做到这一点。由于你预计这个数字可能很大，你想知道它对 $10^9 + 9$ 取模的结果。

Input Format

输入的第一行包含测试用例的数量 $T$。接下来的描述是测试用例：

每个测试用例由三行组成，每行包含一个非空单词——按它们在字典中出现的顺序。单词由小写英文字母和问号组成，问号表示缺失的字符。每个单词最多有 $1,000,000$ 个字符。

Output Format

对于每个测试用例，输出一行，包含将每个问号替换为从 “a” 到 “z” 的 $26$ 个字母之一的不同方法数，使得三个单词不同且按字典顺序排列。结果应对 $10^9 + 9$ 取模。

3
?heoret?cal
c?mputer
?cience
jagiellonian
?niversity
kra?ow
?
b
c

42562
52
1

Hint

题面翻译由 ChatGPT-4o 提供。