쓸데 없이 싸돌아다니기를 좋아하는 kcm1700군이 사악한 KysShadow군에게 납치되었다. 그는 kcm1700군을 총 길이가 N인 아래와 같은 모습의 좁은 복도에 감금시켜놨다.

처음에 KysShadow군은 kcm1700이 왼쪽에서부터 k번째 칸에 있는 것을 보았다. 그런데 시간이 t가 흐른 뒤 그가 다시 kcm1700을 보았을 때는 kcm1700이 l번째 칸에 있는 것을 알게되었다.

kcm1700은 가만히 있는 것을 싫어하기 때문에 그 복도 안에서도 이리저리 움직인다. 물론 쉬기 위해서 멈추기도 한다. kcm1700은 시간이 1이 흐를때마다 한칸 옆으로 이동하거나 제자리에 머물러 있는다. 단 복도의 양쪽 끝에서는 양쪽 끝이 막혀있기 때문에 복도의 안쪽방향으로 한칸 가거나 가만히 있는 두가지 경우 밖에 없다.

그런데.. 잠깐! 여기서 호기심이 많은 KysShadow군은 kcm1700이 처음에 k번째 칸에 있다가 l번째 칸으로 이동하는 경우의 수가 궁금해졌다. 당신도 감금되지 않으려면 그를 위하여 그 경우의 수를 구하는 프로그램을 정확히 짜야한다.

한 줄에 N,t,k,l이 공백을 하나씩 두고 차례로 주어진다.(1 ≤ N ≤ 50,   0 ≤ t ≤ 2^31-1,   1 ≤ k ≤ N,   1 ≤ l ≤ N)

한 줄에 경우의 수를 99999989로 나눈 나머지를 출력한다.

프로그램 및 소스코드 이름 : wander

전체 점수의 40%에 해당하는 테스트 데이터는 t ≤ 500000 이다.

2차원 배열로 풀고 있는데 경우의 수 구하려고 예전에 쓰던 무한루프법 써봤는데 잘 안되네요..

지난주 목요일부터 했는데 너무 헷갈리네요..

어떤 방식으로 풀어야 하나요?

스스로 짜보고 싶은데 진짜 답 안나오네요 도움좀..