Given $M$ points in $N$ dimensional space, find the minimum "surface area" of a hyperrectangle required to contain all $M$ points modulo ${10}^9+7$.

As an example, the "surface area" of a $2$-dimensional hyperrectangle (rectangle) is the sum of its $4$ side lengths. The "surface area" of a $3$-dimensional hyperrectangle (rectangular prism) is the sum of the areas of the $6$ sides of the hyperrectangle.

Input Specification

The first line will contain two space-separated integers, $N,M$ $(2\le N\le 10,1\le M\le {10}^5)$, the number of dimensions and the number of points respectively.

The next $M$ lines will each contain $N$ integers, $a_{i_1},a_{i_2},\dots ,a_{i_N}$ $(-{10}^9\le a_{i_j}\le {10}^9)$.

Output Specification

Output the minimum "surface area" of a hyperrectangle required to contain all $M$ points, modulo ${10}^9+7$.

Subtasks

Subtask 1 [10%]

$N=2$

$M\le 100$

Subtask 2 [20%]

$M\le 100$

Subtask 3 [70%]

No additional constraints.

Sample Input 1

2 4
1 1
3 3
-1 2
0 0

Sample Output 1

14

Sample Input 2

5 3
1 4 2 3 4
0 -129 6 9 0
0 0 -10 9 5

Sample Output 2

183436