marcel

Ever since the exam session started, Marcel's son keeps attending parties over and over. This time around he's facing $N^2$ drinks arranged on $N$ lines, each line having $N$ drinks. We know the content of the drink on position $(i, j)$ as $alc_{ij}$ (integer which can be negative). In one sitting, our character can choose between doing one of the $4$ actions:

• Drinks all the drinks from the first line
• Drinks all the drinks from the first column
• Drinks all the drinks from the last line
• Drinks all the drinks from the last column

Of course, in order to not face shame, he can't conduct an action which would result in him drinking less than $X$ units in one sitting. After the turn, the drinks will be eliminated from the grid and the party goes on. At any moment, our character can stop (mandatory when all drinks are gone).

Task

In the next day, Marcel found from trustworthy sources the values of $N$, $X$ and $alc$ and he's interested in finding the number of ways $ANS$ in which the party could have gone, modulo $10^9 + 7$. Two ways are considered distinct if there is a moment at which Marcel's son chose different actions among the $5$ possible actions (the four actions resulting in him drinking, as well as stopping).

Input data

The first line will contain two numbers, $N$ and $X$, separated by a space. $N$ lines, each of them containing $N$ integers follow. The $j^{th}$ number from line $i$ represents the value of $alc_{ij}$.

Output data

The first line will contain a single number, $ANS$, representing the number of ways in which the party can go, modulo $10^9 + 7$.

Constraints and clarifications

• $1 \leq N \leq 120$
• $-10^9 \leq X \leq 10^9$
• $-10^6 \leq alc_{ij} \leq 10^6$

Example 1

stdin

1 10
23

stdout

5

Explanation

In the first test case the party has only one round, in which the main character can choose between consuming $23$ units (possible in $4$ distinct ways) or stopping right away.

Example 2

stdin

1 23
10

stdout

1

Explanation

In the second test case the consumption of only $10$ units would be shameful, so we only have the option of stopping right away.

Example 3

stdin

2 10
23 23
23 23

stdout

53

Example 4

stdin

3 4
1 4 2
3 9 -6
7 8 5

stdout

62