Birgə qaçış

Bessi və dostları fermalarından uzaqda gizli bir otaqda kilidləniblər və Bessi onların qaçışını planlaşdırmalıdır! Otaq n * k ölçüsündə otaqlardan ibarətdir və bu otaqlar n * k ölçülü düzbucaqlı şəbəkədə yerləşir. Üfüqi və şaquli olaraq qonşu otaqlar arasında qapılar mövcuddur. Hər otaqda dəqiq bir inək var.

Bessi sistemi sındırıb və istənilən qapı alt qrupunu açmağı bacarır, lakin hər qapının açılması üçün ödəniş tələb olunur. İnəklərin qaça bilməsi üçün Bessi kifayət qədər qapı açmalıdır ki, bütün inəklər bir hücrədə toplaşsınlar (yer üzünə çıxmaq üçün kifayət qədər gücləri olsun). Bessi ümumi açma xərcini minimuma endirmək istəyir.

Ancaq vəziyyət çox ciddidir və Bessi yalnız bir qaçış planı ilə kifayətlənə bilməz: ona dəstək lazımdır. Ona minimum xərclə qaçış planlarının sayını hesablamağa kömək edin; iki plan fərqli hesab olunur, əgər bir planda bir qapı açılmalı, digərində isə açılmamalıdır.

Bu rəqəm çox böyük ola biləcəyi üçün, yalnız 10^9 + 7 moduluna görə qalıq çıxarın.

Giriş Məlumatları

Birinci sətir n və k (2 ≤ n ≤ 30000, 2 ≤ k ≤ 6) tam ədədlərini ehtiva edir. Növbəti n sətirin hər biri k - 1 tam ədəd ehtiva edir: üfüqi kənardakı hər girişin açma xərcləri.

Növbəti k sətirin hər biri n - 1 tam ədəd ehtiva edir: şaquli kənardakı hər girişin açma xərcləri.

Bütün xərclər 1 ilə 10^9 daxil olmaqla aralıqdadır.

Çıxış Məlumatları

Bir rəqəm çıxarın: minimum xərclə qaçış planlarının sayını, 10^9 + 7 moduluna görə.

Nümunə

Test 4 * 3 şəbəkəsini təmsil edir.

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

Minimum xərcli hər hansı bir qaçış planı 2 xərcli qapı, 3 xərcli qapı və təxminən doqquz 1 xərcli qapı istifadə edəcək.

Nümunələr