Forgotten Homework

Yesterday was a fun first day of University for Alice. She met so many new people, and there were so many activities to do! But her new teacher was super strict. It was her first day of university, and the teacher still gave them a lecture on linear algebra and matrix multiplication. And not only that, in order to test the new students, the teacher also gave them the following homework due to the next day.

You are given an $n \times n$ matrix $A$ and two indices $i$ and $j$. Calculate the sequence $A^1(i,j), A^2(i,j), ..., A^{2 n}(i,j)$ by hand. In other words, the element on row $i$ and column $j$ in each of the matrices $A^1, A^2, ..., A^{2 n}$. Since these numbers can become very large, you should do all calculations modulo $10^9 + 7$.

Alice, wanting to be a perfect student, definitely did not want to fail this task. So she stayed up all night yesterday doing matrix calculations. But oh no! In the morning, on her way to university, she realizes that she forgot to write down the last number $A^{2n}(i, j)$. And now she has no time left to fix her mistake.

Help Alice calculate the number she is missing!


The first line contains three integers $n$ and $i$ and $j$ ($1 \le n \le 3000$, $1 \le i \le n$, $1 \le j \le n$), given to Alice by her teacher. The second line contains the incomplete sequence of $2 n - 1$ integers $A^1(i,j), A^2(i,j), ..., A^{2 n-1}(i, j)$ calculated by Alice ($0 \leq A^ k(i,j) < 10^9 + 7$ for $k = 1, 2, \ldots , 2 n - 1$). You may assume that Alice made no mistakes calculating the incomplete sequence. The remaining $n$ lines of input each contain $n$ integers, giving the matrix $A$. The $c$’th number in the $r$’th of these lines is the entry $A(r, c)$ in row $r$ column $c$ of $A$ ($0 \leq A(r,c) < 10^9 + 7$).


Output the value of $A^{2 n}(i, j)$ modulo $10^9 + 7$.

Sample Input 1 Sample Output 1
3 1 1
0 2 0 4 0
0 1 1
1 0 0
1 0 0
Sample Input 2 Sample Output 2
1 1 1
CPU Time limit 4 seconds
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in