전화번호

베시는 아홉 개의 버튼이 다음과 같이 배열된 새 휴대폰을 갖게 되었다.

123
456
789

베시는 급하게 주어진 전화번호를 입력하려고 하는데, 시간을 아끼기 위해 한쪽 발굽으로 여러 버튼을 동시에 누르기로 한다. 구체적으로, 베시의 발굽은 숫자 하나를 누르거나, 변을 공유하는 두 숫자(총 열두 가지 가능한 쌍)를 누르거나, 정사각형을 이루는 네 숫자(1245, 2356, 4578, 5689)를 누를 수 있다.

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

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

안타깝게도 베시는 이 작업을 수행하는 자신의 실력을 심하게 과대평가했다. 베시의 발굽이 여러 버튼을 동시에 누르면, 그 숫자들은 모두 임의의 순서로 입력된다. 따라서 베시가 위의 누르기 순서를 시도하면, 실제로는 123596847이나 213659874(또는 다른 많은 가능성 중 하나)가 입력될 수 있다.

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

*참고: 이 문제의 시간 제한은 4초로, 기본값의 두 배이다.*

Problem credits: Nick Wu

채점 방식

• 입력 2-3에서는 모든 전화번호의 길이가 최대 \(8\)이다.
• 입력 4-5에서는 전화번호가 1, 2, 3만 포함한다.
• 입력 6-7에서는 전화번호가 숫자 5를 포함하지 않는다.
• 입력 8-9에서는 전화번호가 5, 6, 8, 9만 포함한다.
• 입력 10-12에서는 문자열 길이의 합이 \(10^2\)를 초과하지 않는다.
• 입력 13-15에서는 문자열 길이의 합이 \(10^3\)을 초과하지 않는다.
• 입력 16-18에서는 문자열 길이의 합이 \(10^4\)를 초과하지 않는다.
• 입력 19-21은 추가 제약이 없다.

Problem credits: Nick Wu

첫째 줄에 독립적으로 풀어야 하는 테스트 케이스의 수 \(T\) (\(1\le T\le 10\))가 주어진다.

다음 \(T\)개의 줄에는 숫자 1부터 9까지로 이루어진 비어 있지 않은 문자열이 한 줄에 하나씩 주어진다. 이 문자열들의 총 길이는 \(10^5\)를 초과하지 않음이 보장된다.

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

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > February > Platinum