Description

Bessie and her friends have been captured and locked in a secret house far away from the farm, and now it is time for Bessie to step up and plan an escape. This house contains $NK$ prison cells arranged in an $N \times K$ rectangular grid. There are doors connecting every pair of horizontally and vertically adjacent cells. Each cell contains one cow.

Bessie has hacked into the system and can unlock any subset of the doors, but each door has a cost. To allow the cows to escape, Bessie must open enough doors so that all cows can gather in a single room (so they will have enough strength to dig a tunnel to the outside). Bessie wants to minimize the total unlocking cost.

However, this mission is extremely important, so Bessie cannot be satisfied with only one escape plan: she also needs backup plans. Help her compute the number of minimum-cost escape plans. If a door is unlocked in one plan but not unlocked in another, then the two plans are considered different.

Since this number can be very large, output it modulo $10^9+7$.

Input Format

The first line contains two space-separated integers $N$ and $K$ ( $2 \leq N \leq 30000$, $2 \leq K \leq 6$ ).

The next $N$ lines each contain $K-1$ space-separated integers, giving the cost to unlock each door on a horizontal edge.

The next $K$ lines each contain $N-1$ space-separated integers, giving the cost to unlock each door on a vertical edge.

All costs are between $1$ and $10^9$.

Output Format

One integer: the number of minimum-cost escape plans, modulo $10^9+7$.

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

10

Hint

This sample describes a $4 \times 3$ grid.

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

All minimum-cost escape plans will use the door with cost $2$, the door with cost $3$, and nine doors with cost $1$. Since there are $10$ ways to choose which cost $1$ door is not used, the answer is $10$.

Subtasks

For $20\%$ of the testdata, it is guaranteed that $N \leq 500$, and all costs are between $1$ and $5$.

For another $20\%$ of the testdata, it is guaranteed that $N \leq 5000$.

Translated by ChatGPT 5