题目描述

淮清终于考完月考了，她都快烦死了，九年级月考的时候七八年级还在开运动会，真的是太不人性了，好在国庆来了。

在国庆期间，淮清有 n 时间段去完成她自己支配，每个时间段她有 k 个选择。每个选择所获得的开心值不一样。

但是淮清又很烦重复做一个种类的事，例如她在第一个时间段做完 a 种类的事情，下一个紧挨着的时间段她就不能再选择 a 种类的事情了。但是在下下一个时间段就可以继续做 a 种类的事。

淮清想要知道她能获得的最大开心值是什么。

输入格式

共 n + 1 行：

第1行：包括两个正整数 n 和 k。

第 2 ~ n + 1 行：是 n 个时间段，包括 k 个整数 $a_{i,j}$，表示该时间段 k 类事情的开心值。

输出格式

输出 nn 件事情后，淮清所得的最大开心值。对 $10^{9}+7$取模。

输入输出样例

输入数据

3 2

1 3

2 5

6 3

输出数据 1

12

提示/说明

本题输入量比较大，建议采取快速读入方式。

对于 20% 的数据：满足 k = 2。

对于 30% 的数据：满足 $1 \le n \le 10^2$

对于 100%100% 的数据：满足 $1 \le n \le 10^4 ,2 \le k \le 10^2,1 \le a_{i,j} \le 10^9$ 。