어휘

프로그래머는 커피만 잔뜩 마시고 아는 단어는 세 개뿐이라는 농담이 있다. 게다가 그 세 단어의 철자마저 자주 틀린다. 그래서 우리는 그 세 단어만 실은 사전을 한 권 펴냈다.

그 사전을 한 권 얻었는데, 얼마 지나지 않아 위에 커피를 쏟았다. 이제 몇몇 글자는 알아볼 수 없다. 다행히 사전에 실린 세 단어는 서로 다르고, 사전답게 사전순으로 인쇄되어 있다.

이 사실로 지워진 글자를 되살리기 전에, 되살리는 방법이 몇 가지인지 알고 싶다. 그 수가 크므로 $10^9 + 9$로 나눈 나머지를 구한다.

첫 줄에 테스트 케이스 개수 $T$가 주어진다. 이어서 테스트 케이스가 하나씩 주어진다.

각 테스트 케이스는 세 줄로 이루어지고, 각 줄에 사전에 실린 순서대로 비어 있지 않은 단어가 하나씩 주어진다. 단어는 영어 소문자와 물음표로 이루어지며, 물음표는 알아볼 수 없는 글자를 뜻한다. 단어 하나의 길이는 최대 1,000,000이다.

각 테스트 케이스마다 한 줄에 답을 출력한다. 답은 물음표를 각각 a부터 z까지 26개 글자 중 하나로 바꿔서 세 단어가 서로 다르고 사전순이 되도록 하는 방법의 수를 $10^9 + 9$로 나눈 나머지다.