현대모비스에서 전기차로 경사로 주행 테스트를 하려고 합니다. 경사로 테스트는 n×m 크기의 격자 형태의 공간에서 진행되며, 각 칸에 적힌 숫자는 높이를 나타냅니다. 전기차는 격자 내의 모든 칸에서 출발 가능하며, 상하좌우로 인접한 칸으로만 이동 가능하고 격자 밖을 벗어날 수는 없습니다. 전기차가 인접한 칸으로 이동하는 길의 경사는 이동하려는 칸의 높이에서 현재 칸의 높이를 뺀 값입니다. 예를 들어 높이가 5인 칸에서 7인 칸으로 이동하는 길의 경사는 2(= 7 - 5)이고, 높이가 6인 칸에서 높이가 1인 칸으로 이동하는 길의 경사는 -5(= 1 - 6)입니다.

경사 수열 d가 주어집니다. 경사 수열은 테스트에서 전기차가 이동할 길의 경사를 나타내며, d[i]는 전기차가 i+1번째로 이동할 때 경사가 d[i]인 길을 지나야 함을 나타냅니다. 전기차가 경사로를 반복적으로 이동할 때 받는 스트레스를 관찰하기 위해 주어진 경사수열을 k번 반복할 수 있는 경로를 찾으려 합니다. 같은 칸을 여러 번 방문하거나 지나온 길을 바로 되돌아가는 경로도 가능합니다.

예를 들어 아래와 같은 격자에서 경사 수열 d = [1, -2, -1, 0, 2]이고 k = 2라고 가정해 보겠습니다. 이 경사 수열을 k = 2 번 반복할 수 있는 경로 중 하나는 아래 그림과 같습니다.

위 경로에서 방문한 칸의 높이는 방문 순서대로 [5, 6, 4, 3, 3, 5, 6, 4, 3, 3, 5]입니다. 길의 경사가 순서대로 [1, -2, -1, 0, 2, 1, -2, -1, 0, 2]으로, d가 2번 반복되었습니다.

격자 칸의 높이를 담은 2차원 정수 배열 grid, 경사 수열을 담은 1차원 정수 배열 d와 경사 수열을 반복하는 횟수를 나타내는 정수 k가 매개변수로 주어집니다. 이때, 격자 내에서 조건을 만족하는 경로의 수를 return 하도록 solution 함수를 완성해 주세요. 단, 답이 커질 수 있으므로 1,000,000,007(= 10⁹ + 7)로 나눈 나머지를 return 해주세요.

제한사항

• 3 ≤ grid의 길이 = n ≤ 8
• 3 ≤ grid[i]의 길이 = m ≤ 8
  • 0 ≤ grid[i][j] ≤ 1,000
  • grid[i][j]는 각자의 i+1번째 행, j+1번째 열에 위치한 칸의 높이를 나타냅니다.
• 1 ≤ d의 길이 ≤ 100
  • -100 ≤ d의 원소 ≤ 100
• 1 ≤ k ≤ 10⁹

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다. 조건을 만족하는 경로의 수는 16가지가 있습니다.
따라서 16을 return 하면 됩니다.

입출력 예 #2

조건을 만족하는 경로의 수는 1가지가 있습니다.
따라서 1을 return 하면 됩니다.

입출력 예 #3

조건을 만족하는 경로의 수는 8,160,249,293,367,222,249,455,616 가지가 있습니다.
따라서 경로의 수를 10⁹ + 7로 나눈 나머지인 595737277을 return 하면 됩니다.