Спільна втеча

Бессі та її друзі були захоплені та замкнені в секретному приміщенні далеко від їхньої ферми, і Бессі повинна спланувати їхню втечу! Приміщення складається з n * k кімнат, розташованих у прямокутній сітці n * k, де між сусідніми кімнатами по горизонталі та вертикалі є ворота. У кожній кімнаті знаходиться рівно одна корова.

Бессі зламала систему і може розблокувати будь-яку підмножину воріт, але за кожні ворота потрібно платити. Щоб корови могли втекти, Бессі повинна відкрити достатньо воріт, щоб усі корови могли зібратися в одній клітинці (щоб у них було достатньо сил вийти на поверхню). Бессі прагне мінімізувати загальну вартість розблокування.

Але ставки вищі, ніж будь-коли, і Бессі не може задовольнитися одним планом втечі: їй потрібна підтримка. Допоможіть їй підрахувати кількість планів втечі з мінімальними витратами; два плани вважаються різними, якщо в одному з планів потрібно відкрити одні ворота, а в іншому ні.

Оскільки це число може бути дуже великим, виведіть лише його залишок за модулем 10^9 + 7.

Вхідні дані

Перший рядок містить два цілих числа n і k (2 ≤ n ≤ 30000, 2 ≤ k ≤ 6). Кожен з наступних n рядків містить k - 1 цілих чисел: витрати на розблокування кожного входу на горизонтальному краю.

Кожен з наступних k рядків містить n - 1 цілих чисел: витрати на розблокування кожного входу на вертикальному краю.

Усі витрати знаходяться в діапазоні від 1 до 10^9 включно.

Вихідні дані

Виведіть одне число: кількість планів втечі з мінімальною вартістю, за модулем 10^9 + 7.

Приклад

Тест представляє собою сітку 4 * 3.

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

Будь-який план втечі з мінімальною вартістю буде використовувати дверний проріз вартістю 2, дверний проріз вартістю 3 та близько дев'яти дверних прорізів вартістю 1.

Приклади