An là một đầu bếp tài giỏi và là một trong số ít người vào được vòng chung kết cuộc thi MathChef. Hôm nay là ngày diễn ra vòng chung kết, ban tổ chức chuẩn bị cho mỗi thí sinh một tủ nguyên liệu gồm \(n \times m\) ô tủ với \(n\) hàng ngang và \(m\) hàng dọc. Ô tủ ở vị trí \((i,j)\) là ô tủ ở hàng thứ \(i\) tính từ trên xuống dưới và cột thứ \(j\) tính từ trái sang phải, mỗi ô tủ \((i, j)\) chứa một loại nguyên liệu khác nhau với số lượng là \(a_{i,j}\).

Cuộc thi sẽ diễn ra như sau, cuộc thi gồm có \(q\) vòng, ở mỗi vòng ban giám khảo sẽ chọn ra một hình tam giác vuông cân có một cạnh song song với đường thẳng ngang và một cạnh song song với đường thẳng đứng và đặt tam giác lên trước tủ nguyên liệu sao cho tam giác khớp với một số ô tủ mà không bị lệch ra ngoài. Dưới đây là ví dụ về các tam giác vuông cân hợp lệ:

Sau đó, họ chọn ra các ô tủ nằm trong tam giác và yêu cầu thí sinh dùng các loại nguyên liệu nằm trong các ô tủ đó với số lượng tùy ý (ít nhất là \(1\) và không vượt quá số lượng ban đầu) để chế biến món ăn.

Biết rằng người làm ra món ăn ngon nhất sẽ được điểm ở vòng thi đó, An cố gắng nghĩ cách chọn và sử dụng nguyên liệu một cách hiệu quả nhất để chiến thắng cuộc thi, nhưng để làm được điều đó anh phải biết được số lượng cách chọn nguyên liệu khác nhau từ yêu cầu của giám khảo. Lưu ý, sau mỗi vòng thi, tủ nguyên liệu của mỗi thí sinh sẽ được làm đầy lại, tức là số lượng nguyên liệu của mỗi ô tủ sẽ trở về ban đầu.

Yêu cầu: Từ mỗi tam giác được chọn bởi ban giám khảo, bạn hãy in ra số lượng cách chọn nguyên liệu khác nhau mà An có thể chọn. Hai cách chọn là khác nhau khi và chỉ khi tồn tại một loại nguyên liệu có số lượng ở hai cách chọn đó là khác nhau.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 1000)\) lần lượt là số hàng và số cột của tủ nguyên liệu.
• Trong \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên \(a_{i,j}\) \((1 \leq a_{i,j} \leq 10^9)\) là số lượng nguyên liệu ở ô \((i,j)\).
• Dòng tiếp theo chứa số nguyên \(q\) \((1 \leq q \leq 2 \times 10^5)\) là số vòng thi của trận chung kết.
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa sáu số nguyên dương \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(x_3\) và \(y_3\) \((1 \leq x_1, x_2, x_3 \leq n, 1 \leq y_1, y_2, y_3 \leq m)\) lần lượt là vị trí ba đỉnh của tam giác là các ô \((x_1, y_1)\), \((x_2, y_2)\) và \((x_3, y_3)\). Dữ liệu đảm bảo ba đỉnh tạo này thành một tam giác vuông cân hợp lệ.

Output

• In ra \(q\) dòng, mỗi dòng in ra số lượng cách chọn nguyên liệu khác nhau, lấy phần dư khi chia cho \(10^9+7\).

Ví dụ

Input

4 5
1 2 3 4 5
5 6 7 8 9
9 8 7 6 5
4 3 2 1 9
5
2 2 2 3 3 2
2 2 3 3 2 3
1 1 4 1 4 4
1 5 1 2 4 5
1 4 3 4 3 2

Output

336
294
362880
16329600
75264

Giải thích

• Dưới đây là các hình tam giác vuông cân ở mỗi vòng thi:

Ràng buộc

• Subtask \(1\) (\(26\%\) số điểm): \(n, m \leq 50\);
• Subtask \(2\) (\(43\%\) số điểm): \(n, m \leq 500\);
• Subtask \(3\) (\(31\%\) số điểm): Không có ràng buộc gì thêm.