Бесси и друзья были схвачены и заперты в секретном помещении вдали от их фермы, и Бесси должна спланировать их побег! Помещение состоит из n * k комнат, расположенных в прямоугольной сетке n * k, где есть ворота между соседними комнатами по горизонтали и вертикали. В каждой комнате содержится ровно одна корова.

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

Но ставки выше, чем когда-либо, и Бесси не может довольствоваться одним планом побега: ей нужна поддержка. Помогите ей подсчитать количество планов побега с минимальными затратами; два плана считаются разными, если в одном из планов нужно открыть одни ворота, а в другом нет.

Поскольку это число может быть очень большим, выведите только его остаток по модулю 109 + 7.

Входные данные

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

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

Все затраты находятся в диапазоне от 1 до 109 включительно.

Выходные данные

Выведите одно число: количество планов побега с минимальной стоимостью, по модулю 109 + 7.

Пример

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

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

Любой план побега с минимальной стоимостью будет использовать дверной проем стоимости 2, дверной проем стоимости 3 и около девяти дверных проемов стоимости 1.