#4043. [Cerc2014] Vocabulary

题目描述

给你三个字符串，这些字符串有些单词模糊不可认了，用"?"来代表。

现在你可以用任意英文小写字母来代表它们。要求是使得给定的三个字符串中

所有的"?"被你认定的字母代替后，各不相同且按字典序出现。问有多少种方式。

输入格式

先给出一个数字N，代表数据组数。

接下来3*N行，每行给出一个字符串。长度<=1000 000

输出格式

输出结果 Mod 10^9+9

样例

样例输入

3   

?heoret?cal   

c?mputer   

?cience   

jagiellonia   

?niversity   

kra?ow   

?   

b   

c 

样例输出

42562   

52   

1

数据范围与提示