beecrowd | 3326
# Keylogger

**Timelimit: 3**

By Cristhian Bonilha Brazil

Lately you have been very curious about your typing speed, and you have been wondering how long it takes for you to press each key on your keyboard, which has **K **keys.

To figure that out, you installed a keylogger on your own computer. It has been registering the delta time between each pair of key presses. After collecting data for a couple of weeks, you now have access to a 2-dimensional matrix **T **with **K **rows and **K **columns. The element at the **i**-th row and **j**-th column is **T _{i}**

Given that your typing speed varies according to the time of the day and your mood, your keylogger has also given you a latency margin error **L**. That means that, for every pair of keys **i **and **j **on your keyboard, it actually takes between **T _{i,j}** −

You classified for the South American ICPC regional competition, and you have been asked to update some of your contact information on the ICPC website. The problem is that you have been studying so hard that you forgot your password. All you remember is that your password has length **N**.

Luckily, your keylogger also has data about the last time you typed your password on that website. So now you have an array **P **with **N **− 1 elements. Each element **P _{i} **represents the delta time between each consecutive key presses from your password. In other words,

You need to recover your password as soon as possible. Your plan now is to try every sequence of keys that is compatible with the information you have. A sequence **S **of length **N **is compatible with **L**, **T**, and **P **if each pair of consecutive keys **S _{i} **and

The first line contains two integers **K **(1 ≤ **K **≤ 750) and **L **(0 ≤ **L **≤ 10^{9} ), indicating respectively how many keys are there on your keyboard and the latency margin error given by your keylogger. The next **K **lines contain **K **integers each, representing the matrix **T**. The **j**-th integer on the **i**-th line is **T _{i,j}** (1 ≤

Output a single line with an integer indicating how many different sequences of keys are compatible with the information you have. Because this number can be very large, output the remainder of dividing it by 10^{9} + 7.

Input Samples | Output Samples |

4 0 1 1 3 5 2 4 4 10 1 1 1 8 5 6 7 8 5 2 3 8 5 |
1 |

3 3 9 10 15 9 13 16 3 5 6 3 10 5 |
0 |

5 1 1 5 6 8 10 1 2 4 5 5 5 5 5 6 8 3 3 3 4 5 1 1 3 4 5 4 1 3 7 |
4 |