Một lưới hình chữ nhật với các chữ cái tiếng Anh viết thường trong mỗi ô được gọi là sắp xếp kép (doubly sorted) nếu trong mỗi hàng, các chữ cái không giảm từ trái sang phải, và trong mỗi cột, các chữ cái không giảm từ trên xuống dưới. Trong các ví dụ sau, hai lưới đầu tiên được sắp xếp kép, trong khi hai lưới còn lại thì không:

abc    ace    aceg    base
def    ade    cdef    base
ghi    bdg    xxyy    base

Bạn được cho một lưới đã điền một phần, trong đó một số ô đã có sẵn chữ cái. Nhiệm vụ của bạn là tính số cách bạn có thể điền vào các ô còn lại để lưới kết quả được sắp xếp kép. Kết quả có thể là một số lớn; bạn cần đưa ra số cách chia dư cho 10007.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, T. T bộ test tiếp nối theo sau. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên R và C, lần lượt là số hàng và số cột. Tiếp theo là R dòng, mỗi dòng chứa một chuỗi có độ dài C, mô tả lưới đã điền một phần. Mỗi ký tự trong lưới là một chữ cái tiếng Anh viết thường, hoặc dấu '.', cho biết ô đó chưa được điền.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng. Dòng đó phải chứa "Case #X: y", trong đó X là số thứ tự bộ test bắt đầu từ 1, và y là số lượng lưới sắp xếp kép có thể có, chia dư cho 10007.

Ràng buộc

• 1 ≤ T ≤ 40.
• Mỗi ký tự trong lưới đã điền một phần là '.' hoặc một chữ cái tiếng Anh viết thường.

Phân nhóm

• Small dataset: 1 ≤ R, C ≤ 4.
• Large dataset: 1 ≤ R, C ≤ 10.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2 2
ad
c.
3 3
.a.
a.z
.z.
4 4
....
.g..
.cj.
....

Case #1: 23
Case #2: 7569
Case #3: 0

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Doubly-sorted Grid.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.