시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 1024 MB 3 2 2 66.667%

## 문제

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 Ti,j, and it represents how long it takes, on average, for you to press the key j right after having pressed the key i. For example, the element T3,5 represents how long it takes, on average, for you to press the key 5 right after having pressed the key 3. Coincidentally, each row on T is ordered non-decreasingly.

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 Ti,j −L and Ti,j +L, inclusive, for you to press the key j right after having pressed the key i.

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 Si and Si+1 satisfy that TSi,Si+1 − L ≤ Pi ≤ TSi,Si+1 + L. How many such sequences are there?

## 입력

The first line contains two integers K (1 ≤ K ≤ 750) and L (0 ≤ L ≤ 109), 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 Ti,j (1 ≤ Ti,j ≤ 109 for i = 1, 2, . . . , K and j = 1, 2, . . . , K). Recall that Ti,j indicates how long it takes, on average, for you to press the key j right after having pressed the key i, and that each row on T is ordered non-decreasingly (Ti,j ≤ Ti,j+1 for i = 1, 2, . . . , K and j = 1, 2, . . . , K − 1). The next line contains an integer N (2 ≤ N ≤ 104), representing the length of your password. The final line contains N − 1 integers P1, P2, . . . , PN−1 (1 ≤ Pi ≤ 109 for i = 1, 2, . . . , N − 1), denoting the delta time between each consecutive key presses from your password.

## 출력

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 109 + 7.

## 예제 입력 1

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


## 예제 출력 1

1


## 예제 입력 2

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


## 예제 출력 2

0


## 예제 입력 3

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


## 예제 출력 3

4