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}, \ldots, 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 further 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