Bessie có một chiếc điện thoại mới với chín nút được bố trí như sau:

123
456
789

Bessie đang vội nhập một số điện thoại cho trước, nên cô quyết định tiết kiệm thời gian bằng cách dùng một móng guốc nhấn nhiều nút cùng lúc. Cụ thể, móng guốc của Bessie có thể nhấn một chữ số; hai chữ số có chung một cạnh (tổng cộng có mười hai cặp như vậy); hoặc bốn chữ số tạo thành một hình vuông (1245, 2356, 4578 hoặc 5689).

Ví dụ, nếu số điện thoại Bessie muốn nhập là 123659874, cô có thể thử tiết kiệm thời gian bằng cách:

1. Nhấn đồng thời 1 và 2.
2. Nhấn 3.
3. Nhấn đồng thời 6, 5, 9 và 8.
4. Nhấn đồng thời 7 và 4.

Đáng tiếc, Bessie đã đánh giá quá cao khả năng thực hiện việc này của mình: nếu móng guốc của cô nhấn nhiều nút cùng lúc thì tất cả các chữ số đó sẽ được nhập theo một thứ tự tùy ý. Vì vậy, nếu Bessie thử chuỗi lần nhấn trên, cô có thể nhập thành 123596847 hoặc 213659874 (hay một trong rất nhiều khả năng khác).

Cho một dãy chữ số mà Bessie đã nhập, hãy đếm số lượng số điện thoại mà cô có thể đã định nhập, lấy modulo \(10^9+7\).

Lưu ý: giới hạn thời gian của bài này là 4 giây, gấp đôi mức mặc định.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10\)), số bộ test độc lập cần giải.

\(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. Bảo đảm tổng độ dài của các chuỗi không vượt quá \(10^5\).

Dữ liệu ra

Với mỗi bộ test, in số lượng số điện thoại Bessie có thể đã định nhập, lấy modulo \(10^9+7\).

Phân nhóm

• Trong các tệp test 2–3, mọi số điện thoại có độ dài không quá \(8\).
• Trong các tệp test 4–5, số điện thoại chỉ chứa 1, 2 và 3.
• Trong các tệp test 6–7, số điện thoại không chứa chữ số 5.
• Trong các tệp test 8–9, số điện thoại chỉ chứa 5, 6, 8 và 9.
• Trong các tệp test 10–12, tổng độ dài các chuỗi không vượt quá \(10^2\).
• Trong các tệp test 13–15, tổng độ dài các chuỗi không vượt quá \(10^3\).
• Trong các tệp test 16–18, tổng độ dài các chuỗi không vượt quá \(10^4\).
• Trong các tệp test 19–21, không có ràng buộc bổ sung.

Ví dụ

5
1478
4455
5968
31313211
123659874

5
2
24
3
255

1478
1487
4178
4187
1748

Nguồn

USACO 2022 February Contest, Platinum — Phone Numbers: https://usaco.org/index.php?page=viewproblem2&cpid=1214

Tác giả: Nick Wu.