Bessie và những người bạn đã bị bắt và giam trong một khu phức hợp bí mật ở nơi cách xa trang trại, và Bessie phải lên kế hoạch trốn thoát cho cả nhóm! Khu phức hợp gồm \(NK\) phòng giam được bố trí thành một lưới hình chữ nhật \(N \times K\), với các cánh cổng nằm giữa những ô kề nhau theo chiều ngang và chiều dọc. Mỗi ô giam đúng một con bò.

Bessie đã xâm nhập được vào hệ thống và có thể mở khóa bất kỳ tập con nào của các cánh cổng, nhưng mỗi cánh cổng có một chi phí. Để những con bò trốn thoát, Bessie phải mở đủ số cổng để tất cả bò có thể tập trung trong một ô duy nhất (nhờ vậy chúng có đủ sức bò để đào đường hầm lên mặt đất!). Bessie muốn giảm thiểu tổng chi phí mở khóa.

Nhưng tình thế nghiêm trọng hơn bao giờ hết, và Bessie không thể hài lòng với chỉ một kế hoạch trốn thoát: cô cần các phương án dự phòng. Hãy giúp cô đếm số kế hoạch trốn thoát có chi phí nhỏ nhất; hai kế hoạch được coi là khác nhau nếu có một cánh cổng cần được mở khóa trong kế hoạch này nhưng không cần được mở khóa trong kế hoạch kia.

Vì số lượng này có thể rất lớn, chỉ in ra số dư của nó khi chia cho \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách \(N\) và \(K\) (\(2 \le N \le 30000, 2 \le K \le 6\)).

Mỗi dòng trong \(N\) dòng tiếp theo chứa \(K-1\) số nguyên cách nhau bởi dấu cách: chi phí mở khóa từng cánh cổng trên một cạnh nằm ngang.

Mỗi dòng trong \(K\) dòng tiếp theo chứa \(N-1\) số nguyên cách nhau bởi dấu cách: chi phí mở khóa từng cánh cổng trên một cạnh thẳng đứng.

Mọi chi phí đều nằm trong khoảng từ \(1\) đến \(10^9\), kể cả hai đầu mút.

Phân nhóm

• Trong 20% số trường hợp kiểm thử, đảm bảo \(N \leq 500\) và mọi trọng số đều nằm trong khoảng từ \(1\) đến \(5\), kể cả hai đầu mút.
• Trong 20% số trường hợp kiểm thử khác, đảm bảo \(N \leq 5000\).

Dữ liệu ra

In ra một số nguyên duy nhất: số kế hoạch trốn thoát có chi phí nhỏ nhất, lấy modulo \(10^{9} + 7\).

Ví dụ

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

10

     1     1
  +-----+-----+
  |     |     |
1 |     |2    | 1
  |  5  |  6  |
  +-----+-----+
  |     |     |
1 |     |3    | 1
  |  7  |  8  |
  +-----+-----+
  |     |     |
1 |     |4    | 1
  |     |     |
  +-----+-----+
     1    1

Nguồn

USACO 2019 US Open Contest, Platinum — Compound Escape

Tác giả: Brian Dean.