Compound 탈출

벳시와 친구들이 농장에서 멀리 떨어진 비밀 수용소에 갇혔으므로, 탈출 계획은 벳시가 세워야 한다. 수용소는 $N \times K$ 격자 모양으로 배치된 $NK$개의 감방으로 이루어진다. 가로와 세로로 인접한 감방 사이에는 문이 있다. 각 감방에는 소가 정확히 한 마리씩 들어 있다.

벳시는 시스템에 침입해 문의 임의의 부분집합을 열 수 있지만, 문마다 여는 비용이 있다. 소들이 탈출하려면 모두 한 감방에 모일 수 있을 만큼 문을 열어야 한다. 벳시는 문을 여는 총 비용을 최소로 하려고 한다.

벳시에게는 예비 계획도 필요하다. 최소 비용으로 탈출하는 계획의 수를 세어라. 한 계획에서는 열리고 다른 계획에서는 열리지 않는 문이 하나라도 있으면 두 계획은 다른 것으로 본다. 이 수는 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에 두 정수 $N$과 $K$가 주어진다 ($2 \le N \le 30000$, $2 \le K \le 6$).

이어지는 $N$개 줄에는 각각 $K-1$개의 정수가 주어지며, 이는 해당 행의 가로 간선에 있는 문을 여는 비용이다.

이어지는 $K$개 줄에는 각각 $N-1$개의 정수가 주어지며, 이는 해당 열의 세로 간선에 있는 문을 여는 비용이다.

모든 비용은 $1$ 이상 $10^9$ 이하의 정수이다.

테스트 케이스의 20%에서는 $N \le 500$이고 모든 비용이 $1$ 이상 $5$ 이하이다. 또 다른 20%에서는 $N \le 5000$이다.

최소 비용 탈출 계획의 수를 $10^9 + 7$로 나눈 나머지 하나의 정수.