정확한 시간에 도착하는 경로의 개수

세준이는 공항으로 정문이를 데리러 가려고 한다. 그런데 정문이의 비행기가 T분 늦게 도착한다는 연락을 받았다. 세준이는 현재 위치에서 출발해 드라이브를 하다가 정확히 T분 뒤에 공항에 도착하려고 한다.

교차점과 도로의 정보는 인접 행렬 A로 주어진다. A[i][j]가 0이면 i번 교차점에서 j번 교차점으로 바로 가는 도로가 없다. A[i][j]가 1 이상 5 이하이면, i번 교차점에서 j번 교차점으로 이동하는 데 정확히 A[i][j]분이 걸리는 도로가 있다는 뜻이다.

시작점 S에서 끝점 E까지 정확히 T분 만에 도착하는 경로의 개수를 구하라.

첫째 줄에 교차점의 개수 N, 시작점 S, 끝점 E, 정문이가 늦는 시간 T가 공백으로 주어진다. N은 10 이하의 자연수이고, S와 E는 1 이상 N 이하의 자연수이다. T는 1 이상 1,000,000,000 이하의 자연수이다.

둘째 줄부터 N개의 줄에 길의 정보가 주어진다. 각 줄은 길이가 N인 숫자 문자열이며, i번째 줄의 j번째 숫자가 A[i][j]이다.

S에서 출발해 정확히 T분 뒤에 E에 도착하는 경로의 개수를 1,000,003으로 나눈 나머지를 출력한다.