Number of Routes Arriving at the Exact Time

Sejun is going to the airport to pick up Jeongmun. He has just heard that Jeongmun's flight will arrive T minutes late. Sejun wants to leave his current position, drive around, and arrive at the airport exactly T minutes later.

The intersections and roads are given as an adjacency matrix A. If A[i][j] is 0, there is no direct road from intersection i to intersection j. If A[i][j] is between 1 and 5, there is a road from intersection i to intersection j that takes exactly A[i][j] minutes.

Count the number of routes from the starting point S to the ending point E that arrive in exactly T minutes.

The first line contains four integers: the number of intersections N, the starting point S, the ending point E, and the delay time T. N is a positive integer not greater than 10. S and E are positive integers between 1 and N. T is a positive integer not greater than 1,000,000,000.

The next N lines describe the roads. Each line is a string of N digits, and the j-th digit on the i-th line is A[i][j].

Print the number of routes that start at S and arrive at E exactly T minutes later, modulo 1,000,003.