시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 127 33 27 27.000%

문제

세준이는 정문이를 데리러 공항으로 가기로 했다. 하지만, 방금 세준이는 정문이의 비행기가 연착된다는 전화를 받았다. 세준이는 정문이가 정확하게 몇 분 늦는지 알고 있고, 그 시간동안 밖에서 드라이브를 하려고 한다. 정문이가 늦는 시간을 T라고 하자.

세준이는 자기가 지금 있는 위치에서부터, 공항까지 정확하게 T분만에 도착하는 길의 개수를 구하고 싶다.

길의 정보는 인접행렬로 주어진다. A[i][j]가 0이라면 i에서 j로 가는 길이 없는 것이고, A[i][j] <=5라면, i에서 j로 걸리는 시간이 그만 큼 걸리는 것 있는 것이다.

입력

첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 길의 정보가 주어진다.

출력

첫째 줄에 길의 경우의 수를 1000003로 나눈 나머지를 출력한다.

예제 입력

3 1 3 5
012
201
120

예제 출력

8

힌트

출처