Беси с друзьями попала в ловушку и разрабатывает план побега.
Ловушка состоит из \(NK\) ячеек, в виде прямоугольной решётки \(N \times K\).
В каждой ячейке имеется проход между горизонтально и вертикально соседними
ячейками. В каждой ячейке находится ровно одна корова.
Беси способна разблокировать любое подмножество проходов, но имеется стоимость
разблокировки каждого прохода. Чтобы сбежать, коровам достаточно собраться в одной
ячейке. Бесси хочет минимизировать стоимость открытия проходов для сбора в одной
ячейке.
Кроме того, Беси должна посчитать количество планов с минимальной стоимостью
открытия проходов. Два плана рассматриваются как различные, если есть проход который
нужно открыть в одном плане и не нужно в другом.
Поскольку это число может быть очень большим, выводите его остаток по модулю
\(10^9 + 7\).
ФОРМАТ ВВОДА (файл escape.in):
Первая строка ввода содержит два разделённых пробелом целых числа
\(N\) и
\(K\)
(
\(2 \le N \le 30000, 2 \le K \le 6\)).
Каждая из последующих \(N\) строк содержит \(K-1\) целое число - стоимости
разблокирования каждого прохода в горизонтальном направлении.
Каждая из последующих \(K\) строк содержит \(N-1\) целое число - стоимости
разблокирования каждого прохода в вертикальном направлении.
Все стоимости от \(1\) до \(10^9\) включительно.
В 20% тестов гарантируется, что \(N \leq 500\) и все веса от \(1\) до \(5\) включительно.
В других 20% тестов гарантируется \(N \leq 5000\).
ФОРМАТ ВЫВОДА (файл escape.out):
Одно целое число - количество планов минимальной стоимости по модулю \(10^{9} + 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 1
5 6
7 8
1 1
1 1 1
2 3 4
1 1 1
|
10
|