[Cerc2014] Vocabulary

时间限制:5s      空间限制:128MB

题目描述

给你三个字符串,这些字符串有些单词模糊不可认了,用"?"来代表。 
现在你可以用任意英文小写字母来代表它们。要求是使得给定的三个字符串中 
所有的"?"被你认定的字母代替后,各不相同且按字典序出现。问有多少种方式。 


输入格式

先给出一个数字N,代表数据组数。 
接下来3*N行,每行给出一个字符串。长度<=1000 000 


输出格式

输出结果 Mod 10^9+9 


样例输入

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

样例输出

42562 
52 
1

提示

没有写明提示


题目来源

没有写明来源