잊어버린 숙제

어제는 Alice가 대학에 입학한 즐거운 첫날이었다. 새로운 사람을 아주 많이 만났고, 할 활동도 많았다! 하지만 새 선생님은 무척 엄격했다. 대학 첫날인데도 선생님은 선형대수와 행렬 곱셈에 대한 강의를 했다. 뿐만 아니라 신입생을 시험하려고 다음 날까지 내주는 숙제를 냈다.

$n \times n$ 행렬 $A$와 두 인덱스 $i$, $j$가 주어진다. 수열 $A^1(i,j), A^2(i,j), ..., A^{2 n}(i,j)$를 손으로 계산하라. 즉, 행렬 $A^1, A^2, ..., A^{2 n}$ 각각에서 $i$행 $j$열에 있는 원소를 계산하라. 이 수는 아주 커질 수 있으므로 모든 계산은 $10^9 + 7$로 나눈 나머지로 하라.

완벽한 학생이 되고 싶었던 Alice는 이 과제를 절대 실패하고 싶지 않았다. 그래서 어제 밤을 새며 행렬 계산을 했다. 그런데 이런! 아침에 대학으로 가는 길에 마지막 수 $A^{2n}(i, j)$를 적지 않았다는 사실을 깨달았다. 이제 실수를 고칠 시간도 없다.

Alice가 빠뜨린 수를 계산하도록 도와주자!

첫째 줄에 세 정수 $n$, $i$, $j$가 주어진다 ($1 \le n \le 3000$, $1 \le i \le n$, $1 \le j \le n$). 이는 선생님이 Alice에게 준 값이다. 둘째 줄에 Alice가 계산한 $2 n - 1$개의 정수로 이루어진 불완전한 수열 $A^1(i,j), A^2(i,j), ..., A^{2 n-1}(i, j)$이 주어진다 ($0 \leq A^k(i,j) < 10^9 + 7$ for $k = 1, 2, \ldots, 2 n - 1$). Alice가 이 불완전한 수열을 계산할 때 실수하지 않았다고 가정할 수 있다. 이어서 $n$개의 줄에 각각 $n$개의 정수가 주어지며, 이는 행렬 $A$를 나타낸다. 이 $n$개의 줄 중 $r$번째 줄의 $c$번째 수는 $A$의 $r$행 $c$열 성분 $A(r, c)$이다 ($0 \leq A(r,c) < 10^9 + 7$).

$A^{2 n}(i, j)$를 $10^9 + 7$로 나눈 나머지를 출력한다.