전화번호

베시는 아래와 같이 버튼 9개가 배열된 새 휴대폰을 갖고 있다.

123
456
789

베시는 전화번호를 서둘러 입력하려고 발굽 하나로 버튼 여러 개를 동시에 눌러 시간을 줄인다. 발굽은 숫자 하나를 누르거나, 변을 공유하는 숫자 두 개를 누르거나(총 12가지 쌍), 정사각형을 이루는 숫자 네 개(1245, 2356, 4578, 5689)를 누를 수 있다.

예를 들어 베시가 입력하려는 전화번호가 123659874라면, 베시는 다음과 같이 누를 수 있다.

1. 1과 2를 동시에 누른다.
2. 3을 누른다.
3. 6, 5, 9, 8을 동시에 누른다.
4. 7과 4를 동시에 누른다.

하지만 베시는 자신의 실력을 크게 과대평가했다. 발굽으로 여러 버튼을 동시에 누르면 그 숫자들은 임의의 순서로 입력된다. 따라서 위 순서대로 누르면 123596847이나 213659874 등 다른 여러 결과가 나올 수 있다.

베시가 입력한 숫자열이 주어질 때, 베시가 입력하려고 했을 수 있는 전화번호의 개수를 $10^9+7$로 나눈 나머지를 구하라.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어진다.

이어지는 $T$개 줄에는 각각 1부터 9까지의 숫자로 이루어진 비어 있지 않은 문자열이 주어진다. 이 문자열들의 길이 합은 $10^5$를 넘지 않는다.

각 테스트 케이스마다 베시가 입력하려고 했을 수 있는 전화번호의 개수를 $10^9+7$로 나눈 나머지를 출력한다.

첫 번째 경우에 베시가 입력하려고 했을 수 있는 전화번호는 다음 5개이다.

1478
1487
4178
4187
1748

예를 들어 베시가 4187을 입력하려고 했다면, 1과 4를 동시에 누르고 이어서 7과 8을 동시에 누를 수 있다.

세 번째 경우에는 숫자들이 정사각형을 이루므로, 베시가 입력하려고 했을 수 있는 전화번호는 입력 숫자열의 모든 순열이다.