Спільна втеча#10326
Бессі та її друзі були захоплені та замкнені в секретному приміщенні далеко від їхньої ферми, і Бессі повинна спланувати їхню втечу! Приміщення складається з n \cdot k кімнат, розташованих у прямокутній сітці n \times k, де між сусідніми кімнатами по горизонталі та вертикалі є ворота. У кожній кімнаті знаходиться рівно одна корова.
Бессі зламала систему і може розблокувати будь-яку підмножину воріт, але за кожні ворота потрібно платити. Щоб корови могли втекти, Бессі повинна відкрити достатньо воріт, щоб усі корови могли зібратися в одній клітинці (щоб у них було достатньо сил вийти на поверхню). Бессі прагне мінімізувати загальну вартість розблокування.
Але ставки вищі, ніж будь-коли, і Бессі не може задовольнитися одним планом втечі: їй потрібна підтримка. Допоможіть їй підрахувати кількість планів втечі з мінімальними витратами; два плани вважаються різними, якщо в одному з планів потрібно відкрити одні ворота, а в іншому ні.
Оскільки це число може бути дуже великим, виведіть лише його залишок за модулем 10^9 + 7.
Перший рядок містить два цілих числа і (2 \leq n \leq 30000, 2 \leq k \leq 6). Кожен з наступних рядків містить k - 1 цілих чисел: витрати на розблокування кожного входу на горизонтальному краю.
Кожен з наступних рядків містить n - 1 цілих чисел: витрати на розблокування кожного входу на вертикальному краю.
Усі витрати знаходяться в діапазоні від до 10^9 включно.
Виведіть одне число: кількість планів втечі з мінімальною вартістю, за модулем 10^9 + 7.
Приклад 1
Тест представляє собою сітку 4 \times 3.
1 1
+-----+-----+
| | |
1 | |2 | 1
| 5 | 6 |
+-----+-----+
| | |
1 | |3 | 1
| 7 | 8 |
+-----+-----+
| | |
1 | |4 | 1
| | |
+-----+-----+
1 1Будь-який план втечі з мінімальною вартістю буде використовувати дверний проріз вартістю , дверний проріз вартістю та близько дев'яти дверних прорізів вартістю . Є десять варіантів вибору, яке ребро вартістю не використовувати, тому відповідь — .