Đếm Cây Khung Nhỏ Nhất

Có một lưới $N\times K$ ô. Mỗi cặp ô kề nhau (theo hàng hoặc cột) được ngăn cách bởi một cửa có chi phí mở. Bạn cần chọn một tập cửa tối thiểu để tất cả $N\times K$ ô thông nhau (cây khung nhỏ nhất). Hãy đếm số cách chọn tập cửa đó (số cây khung nhỏ nhất khác nhau), lấy kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$, $K$ ($2\le N\le 30000$, $2\le K\le 6$)
• $N$ dòng tiếp theo, mỗi dòng $K-1$ số nguyên: chi phí cửa ngang trong hàng đó (từ trái sang phải)
• $K$ dòng tiếp theo, mỗi dòng $N-1$ số nguyên: chi phí cửa dọc trong cột đó (từ trên xuống)

Dữ liệu ra

Số cây khung nhỏ nhất, modulo ${10}^9+7$.

Ràng buộc

• $2\le N\le 30000$, $2\le K\le 6$
• Chi phí cửa: $1\le w\le {10}^9$

Ví dụ