Subtask 1 (26% số điểm): \(n, m ≤ 50\).

Với mỗi truy vấn, duyệt và tính tích mọi ô nằm trong tam giác vuông cân.

Độ phức tạp: \(O(q × n^2)\).

Subtask 2 (43% số điểm): n, m ≤ 500

Ta sẽ tính trước tích tiền tố của từng cột, gọi \(p_{i,j}\) là tích tiền tố của cột \(j\) từ hàng \(1\) đến hàng \(i\), khi đó \(p_{i,j} = (a_{1,j} × a_{2,j} × . . . × a_{i,j})\ \ mod\ \ (10^9 + 7)\). Để lấy được tích từ ô \(a_{i,j}\) đến ô \(a_{k,j}\) (i ≤ k), ta có công thức \(p_{k,j} ÷ p_{i−1,j}\), nhưng vì kết quả có chia lấy dư cho \(10^9 + 7\) nên ta phải tính nghịch đảo của \(p_{i−1,j}\) trước. Để tính nghịch đảo của \(p_{i−1,j}\), ta có thể dùng định lý Fermat nhỏ với công thức là \(inv_{i−1,j} = {p_{i-1,j}^{10^9+5}} mod (10^9 + 7)\). Nhưng nếu làm vậy thì độ phức tạp sẽ là \(O(n^2 × log_2(10^9 + 5))\).

Cách tối ưu là ta sẽ tính mảng \(p\) trước với độ phức tạp \(O(n^2)\), sau đó với mỗi cột \(j\), đầu tiên ta tính \(inv_{n,j} = {p_{n,j}^{10^9+5}}\), tiếp theo tính \(inv_{n−1,j} = inv_{n,j} ∗ a_{n,j}\ \ mod\ \ (10^9 + 7), inv_{n−2,j} = inv_{n−1,j} ∗ a_{n−1,j}\ \ mod\ \ (10^9 + 7), . . .\) Cứ như vậy ta sẽ tính được mảng \(inv\) với độ phức tạp \(O(n^2).\) Với mỗi truy vấn, duyệt từng cột của tam giác cân và tính tích của các ô trong cột nằm trong tam giác vuông cân đó.

Độ phức tạp: \(O(n^2 + q × n).\)

Subtask 3 (31% số điểm): Không có ràng buộc gì thêm.

Đối với các tam giác có cạnh huyền cùng phương với đường chéo chính (đường chéo có phương từ trái trên đến phải dưới), thay vì tính tích các cột, ta sẽ tính tích các đường chéo. Với mỗi đường chéo (theo phương của đường chéo chính), ta tính tích tiền tố theo hướng từ trái trên đến phải dưới, tức là \(p_{i,j} = p_{i−1,j−1} × a_{i,j}\ \ mod\ \ (10^9 + 7)\). Khi đó ta có thể trả lời từng truy vấn tương tự như cách ở \(subtask 2\), nhưng độ phức tạp sẽ là \(O(q × n)\). Nhận thấy rằng ta có thể:

• Tính tích từ \(p_{i,j}\) đến \(p_{i,k} (j ≤ k)\) bằng cách tính trước tích tiền tố \(pr_{i,j} = pr_{i,j−1} × p_{i,k}\ \ mod\ \ (10^9 + 7)\).
• Tính tích từ \(p_{i,j}\) đến \(p_{k,j} (i ≤ k)\) bằng cách tính tích tiền tố \(pc_{i,j} = pc_{i−1,j}×p_{i,k}\ \ mod\ \ (10^9+7)\).
• Tính được giá trị nghịch đảo của \(pr_{i,j}\) và \(pc_{i,j}\). Khi đó ta có thể trả lời mỗi truy vấn trong \(O(1)\). Các tam giác có cạnh huyền cùng phương với đường chéo phụ được xử lý tương tự như trên, nhưng ta phải tính tích tiền tố theo hướng từ phải trên đến trái dưới.

Độ phức tạp: \(O(n^2 + q).\)