문제
Bessie는 다음과 같이 배열된 9개의 버튼이 있는 새 전화기를 받았습니다.
123
456
789
Bessie는 주어진 전화번호를 빠르게 입력하려고 하므로 한 발굽으로 여러 버튼을 눌러 시간을 절약하기로 결정합니다. 구체적으로, 베시의 발굽은 한 면을 공유하는 두 개의 숫자(총 12개의 가능한 쌍이 있음) 또는 정사각형을 형성하는 네 개의 숫자(1245, 2356, 4578 또는 5689)를 누를 수 있습니다.
예를 들어 Bessie가 입력하려는 전화번호가 123659874인 경우 시간을 절약하기 위해
1과 2를 동시에 누릅니다.
3을 누릅니다.
6, 5, 9, 8을 동시에 누릅니다.
7과 4를 동시에 누릅니다.
불행히도 Bessie는 이 작업에 대한 그녀의 기술 수준을 크게 과대평가했습니다. Bessie의 발굽이 동시에 여러 버튼을 눌렀다면 모든 숫자를 임의의 순서로 입력할 수 있었습니다. 따라서 Bessie가 위의 순서대로 키를 누르려고 하면 결국 123596847 또는 213659874(또는 다른 여러 가능성 중 하나)를 입력하게 될 수 있습니다.
Bessie가 입력한 일련 번호가 주어지면 입력을 시도할 수 있는 전화 번호의 수를 세고 답은 모듈로 109+7입니다.
입력
입력의 첫 번째 줄에는 독립적으로 해결해야 하는 하위 테스트 케이스의 수인 T(1≤T≤10)가 포함됩니다.
다음 T 라인에는 각각 1에서 9까지의 비어 있지 않은 문자열이 포함되어 있습니다. 입력은 모든 문자열의 길이가 105를 초과하지 않도록 보장합니다.
출력
각 하위 테스트 사례에 대해 입력을 시도할 수 있는 전화번호의 수를 출력하고 답은 모듈로 109+7입니다.
예제1
5
1478
4455
5968
31313211
123659874
5
2
24
3
255