long-walks-from-office-to-home-sweet-home-1

Being in a long distance relationship, giving time to your girlfriend, focusing on your job and maintaining fitness, doing all three of these is not an easy task.
So, to save time, Pankaj has decided to multi task some things together. Now job and girlfriend are a very deadly mix, so he has decided to walk from his office to his house while talking/chatting with his girlfriend at the same time (he will look around for traffic and make sure he doesn't get hit by a car or a bus). 

Now, there are certain landmarks in the city and there are roads connecting these landmarks where he can walk in either direction. Now, to avoid going through the same path every day (well it will become boring at some time), Pankaj has decided to compute how many distinct walks he can take from his office to his house. He knows it takes one unit of time to walk on any road between the landmarks and he knows that his girlfriend will be free for only a certains units of time (She has other things to do like studying, gossiping with other girls etc). So, instead of wasting any time, he would like to travel on only that many roads.

Given the map of the city where he lives, with n landmarks, his office location u (meaning his office is the u^th landmark), location of his house v (meaning his house is the v^th landmark) and k (the exact number of roads he would like to travel), 
find the number of distinct walks from u to v in the city with exactly k number of roads on the walk. Since this number can be too long, find the result modulo 1000000007. 
He will consider two walks are distinct if either they use different road or the sequence of roads on the walks is different. 
Input

The first line of the input will consist of T, the number of test cases.
Each test case will be as follows:
First line of each test case contains four space separated integers n, k, u and v.
Then n lines follow, each line contains n space separated integers with value either 0 or 1. If the j^th integer in the i^th line is 1, it means there is a road connecting landmark i with landmark j, otherwise it the integer is 0, there is no connecting road between them.

Output:
T lines, each containing the required answer.
Constraints
0 < T ≤ 50
1 < n ≤ 50
0 ≤ k ≤ 10^18
0 ≤ u ≤ N-1
0 ≤ v ≤ N-1

SAMPLE INPUT
2
3 1 2 1
0 1 1
1 0 1
1 1 0
4 4 0 3
0 0 0 1
0 0 1 0
0 1 0 1
1 0 1 0

SAMPLE OUTPUT
1
0

Source: hackerearth | Difficulty: MEDIUM
Tags: Matrices


Solutions: