题目描述

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

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

输入格式

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

接下来 $3\times n$ 行，每行给出一个字符串 $S$。

输出格式

输出结果 $\bmod 10^9+9$

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

42562
52
1

数据范围

对于 $100\%$ 的数据，$|S|\le 10^6$。