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

Một tầng hầm gồm $N\times K$ căn phòng xếp thành lưới $N$ hàng, $K$ cột. Hai phòng kề nhau (cùng hàng và kề cột, hoặc cùng cột và kề hàng) được ngăn bởi đúng một cánh cửa, mỗi cửa có chi phí mở riêng.

Bạn muốn mở một tập cửa sao cho từ phòng bất kỳ đều đi được tới mọi phòng còn lại, với tổng chi phí nhỏ nhất có thể. Nói cách khác, tập cửa được mở là một cây khung nhỏ nhất của lưới.

Hãy đếm số tập cửa khác nhau thoả mãn điều kiện trên (hai tập khác nhau nếu có ít nhất một cánh cửa thuộc tập này mà không thuộc tập kia), lấy phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$, $K$.
• $N$ dòng tiếp theo, dòng thứ $i$ gồm $K-1$ số nguyên: chi phí các cửa ngang của hàng $i$, từ trái sang phải (số thứ $j$ là cửa giữa phòng $(i,j)$ và $(i,j+1)$).
• $K$ dòng tiếp theo, dòng thứ $j$ gồm $N-1$ số nguyên: chi phí các cửa dọc của cột $j$, từ trên xuống dưới (số thứ $i$ là cửa giữa phòng $(i,j)$ và $(i+1,j)$).

Dữ liệu ra

Một số nguyên duy nhất: số cây khung nhỏ nhất, lấy modulo ${10}^9+7$.

Ràng buộc

• $2\le N\le 30000$
• $2\le K\le 6$
• Chi phí mỗi cửa là số nguyên $w$ với $1\le w\le {10}^9$

Ví dụ