Số Điện Thoại

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie có một bàn phím số điện thoại với các số $1$ - $9$ được sắp xếp trong lưới $3 \times 3$ :

$\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}$

Mỗi lần nhấn, Bessie có thể:

Nhấn một phím đơn lẻ (ví dụ: $5$ ).
Nhấn hai phím liền kề (chia sẻ cạnh chung) cùng lúc (ví dụ: $1$ và $2$ , hoặc $2$ và $5$ ).
Nhấn bốn phím tạo thành hình vuông $2 \times 2$ cùng lúc (ví dụ: $1, 2, 4, 5$ ).

Khi Bessie nhấn nhiều phím cùng lúc, các chữ số tương ứng xuất hiện trong chuỗi đầu ra theo thứ tự tùy ý (bất kỳ hoán vị nào đều có thể xảy ra).

Cho chuỗi chữ số mà Bessie đã gõ ra, hãy đếm có bao nhiêu số điện thoại gốc khác nhau mà Bessie có thể đã cố gắng gõ để tạo ra chuỗi đầu ra này.

Hai số điện thoại gốc được coi là khác nhau nếu chúng khác nhau về số lần nhấn, hoặc ở một lần nhấn nào đó, tập phím được nhấn khác nhau.

Dữ liệu vào

Dòng đầu tiên: số nguyên $T$ ( $1 \leq T \leq 10$ ), số lượng test case.
$T$ dòng tiếp theo, mỗi dòng chứa một chuỗi không rỗng gồm các chữ số từ $1$ đến $9$ .
Tổng độ dài tất cả các chuỗi không vượt quá $10^{5}$ .

Dữ liệu ra

Với mỗi test case, in ra số lượng số điện thoại gốc có thể, lấy dư cho $10^{9} + 7$ .

Ràng buộc

$1 \leq T \leq 10$
Mỗi chuỗi chỉ chứa các chữ số $1$ - $9$ và không rỗng.
Tổng độ dài tất cả các chuỗi $\leq 10^{5}$ .

Các cặp phím liền kề (chia sẻ cạnh):

$(1, 2), (2, 3), (4, 5), (5, 6), (7, 8), (8, 9), (1, 4), (2, 5), (3, 6), (4, 7), (5, 8), (6, 9)$

Các bộ bốn phím hình vuông $2 \times 2$ :

${1, 2, 4, 5}, {2, 3, 5, 6}, {4, 5, 7, 8}, {5, 6, 8, 9}$

Ví dụ

Input	Output	Giải thích
5 1478 4455 5968 31313211 123659874	5 2 24 3 255	Với chuỗi "1478", có 5 cách: (1)(4)(7)(8), (1)(4)(78), (1)(4)(87), (1)(47)(8), (14)(7)(8). Với "4455", có 2 cách: (4)(4)(5)(5) và (4)(45)(5).

Ghi chú

Lưu ý rằng khi nhấn nhiều phím cùng lúc, các chữ số có thể xuất hiện theo bất kỳ thứ tự nào. Ví dụ, nhấn ${7, 8}$ có thể tạo ra "78" hoặc "87" trong chuỗi đầu ra.

Bình luận

Không có bình luận tại thời điểm này.