Bessie’s Escape Plan

Bessie and her friends have been captured and locked away in a secret house far from the farm. The house contains \(NK\) prison cells arranged in an \(N \times K\) rectangular grid. Each cell houses a cow, and adjacent cells (horizontally or vertically) are connected by doors. Each door has a cost to unlock.

After hacking into the system, Bessie can unlock any subset of doors; however, to escape, she must open enough doors so that all cows can gather in one room (so they have enough strength to dig a tunnel out). Bessie wants the total unlocking cost to be minimized. Moreover, she needs a backup plan – so she also wants to know the number of different ways to achieve this minimum total cost. Two plans are considered different if there exists at least one door that is unlocked in one plan but locked in the other.

Since the number of plans might be huge, output the answer modulo \(10^9+7\).

inputFormat

The first line contains two integers \(N\) and \(K\), representing the number of rows and columns of cells.

The next \(N\) lines each contain \(K-1\) integers. The \(i\)-th of these lines describes the horizontal door unlocking costs in row \(i\): the \(j\)-th integer is the cost to unlock the door between cell \((i,j)\) and cell \((i,j+1)\).

The following \(N-1\) lines each contain \(K\) integers. The \(i\)-th of these lines describes the vertical door unlocking costs between row \(i\) and row \(i+1\): the \(j\)-th integer is the cost to unlock the door between cell \((i,j)\) and cell \((i+1,j)\).

outputFormat

Output a single integer — the number of different minimum-cost escape plans modulo \(10^9+7\).

sample

2 2
1
2
3 4

1