키로거

요즘 타자 속도가 궁금해져서, K개의 키가 있는 키보드에서 각 키를 누르는 데 걸리는 시간이 얼마나 되는지 알고 싶어졌다.

이를 알아내기 위해 자신의 컴퓨터에 키로거를 설치했다. 키로거는 연속한 두 키 입력 사이의 시간 차이를 기록한다. 몇 주 동안 데이터를 모은 결과, 이제 K개의 행과 K개의 열로 이루어진 2차원 행렬 T를 얻었다. i번째 행 j번째 열의 원소는 Ti,j이며, 이는 키 i를 누른 직후 키 j를 누르는 데 평균적으로 걸리는 시간을 나타낸다. 예를 들어 T3,5는 키 3을 누른 직후 키 5를 누르는 데 평균적으로 걸리는 시간이다. 우연히도 T의 각 행은 비감소 순서로 정렬되어 있다.

타자 속도는 하루 중 시간과 기분에 따라 달라지므로, 키로거는 지연 여유 오차 L도 함께 알려준다. 즉, 키보드의 모든 키 쌍 i, j에 대해, 키 i를 누른 직후 키 j를 누르는 데 걸리는 시간은 Ti,j − L 이상 Ti,j + L 이하이다.

남미 ICPC 지역 대회에 진출하게 되어 ICPC 웹사이트에서 연락처 정보 일부를 갱신해야 한다. 문제는 너무 열심히 공부한 나머지 비밀번호를 잊어버렸다는 것이다. 기억나는 것은 비밀번호의 길이가 N이라는 것뿐이다. 다행히 키로거에는 해당 웹사이트에서 마지막으로 비밀번호를 입력했을 때의 데이터도 있다. 그래서 이제 N − 1개의 원소를 가진 배열 P가 있다. 각 원소 Pi는 비밀번호의 연속한 키 입력 사이의 시간 차이를 나타낸다. 즉, P1은 비밀번호의 첫 번째 문자와 두 번째 문자에 해당하는 키를 누른 사이의 시간 차이이고, P2는 비밀번호의 두 번째 문자와 세 번째 문자에 해당하는 키를 누른 사이의 시간 차이이며, 이런 식이다. P에는 지연 L이 적용되지 않는다. 각 Pi는 평균이 아니라 정확하게 측정된 단일 시간 차이이기 때문이다.

가능한 한 빨리 비밀번호를 되찾아야 한다. 이제 가지고 있는 정보와 호환되는 모든 키 순서를 시도해 보려고 한다. 길이 N의 순서 S가 L, T, P와 호환된다는 것은, 연속한 각 키 쌍 Si와 Si+1에 대해 TSi,Si+1 − L ≤ Pi ≤ TSi,Si+1 + L을 만족한다는 뜻이다. 이러한 순서는 모두 몇 개인가?

첫째 줄에 두 정수 K (1 ≤ K ≤ 750)와 L (0 ≤ L ≤ 109)이 주어지며, 각각 키보드에 있는 키의 개수와 키로거가 알려준 지연 여유 오차를 나타낸다. 다음 K개의 줄에는 K개의 정수가 주어지며 행렬 T를 나타낸다. i번째 줄의 j번째 정수는 Ti,j이다 (1 ≤ Ti,j ≤ 109, i = 1, 2, . . . , K, j = 1, 2, . . . , K). Ti,j는 키 i를 누른 직후 키 j를 누르는 데 평균적으로 걸리는 시간을 나타내며, T의 각 행은 비감소 순서로 정렬되어 있다 (Ti,j ≤ Ti,j+1, i = 1, 2, . . . , K, j = 1, 2, . . . , K − 1). 다음 줄에는 정수 N (2 ≤ N ≤ 104)이 주어지며, 비밀번호의 길이를 나타낸다. 마지막 줄에는 N − 1개의 정수 P1, P2, . . . , PN−1이 주어지며 (1 ≤ Pi ≤ 109, i = 1, 2, . . . , N − 1), 비밀번호의 연속한 키 입력 사이의 시간 차이를 나타낸다.

가지고 있는 정보와 호환되는 서로 다른 키 순서의 개수를 한 줄에 정수로 출력한다. 이 수는 매우 클 수 있으므로 109 + 7로 나눈 나머지를 출력한다.