koi4u에서 문제 풀다가 막히는 부분이 있어서 질문드립니다.

Wander
시간제한
메모리제한
1000 ms
65536 K

설명
쓸데 없이 싸돌아다니기를 좋아하는 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 이다.

값이 너무 커서 float로 처리 했는데 float라 나머지를 구하는게 안되네요.
무엇으로 해야할지 모르겠습니다.
(코드를 나름대로 짜 보앗는데 생각보다 짧게 나왔습니다. 메모리 제한이 있는걸로 보아 배열 사용해서 풀어야 할것 같은데 어떤 방법을 사용해야 할까요?)

#include <stdio.h>
void main()
{
 float n,t,k,l,i,cou=1,r;
 scanf("%f %f %f %f",&n,&t,&k,&l);

 for(i=k;i<l;i++)
 {
  t-=1;
 }

 for(;;)
 {
  if(t==0)
  {
   break;
  }
  t-=1;
  cou*=l-k+1;
 }

 //cou%=99999989;

 printf("%f\\n",cou);
}

//부분만 제대로 작동하면 답이 제대로 나올텐데 float는 나머지 연산자를 지원하지 않는것 같습니다.
if문으로 99999989보다 작아질때까지 빼는 방법도 써 보았는데 값이 커지면 그것도 안되네요..

더블  사용하려고 해봤는데 더블은 이유는 모르겠지만 무한루프되네요. 어디를 수정해야 할까요?

int 사용시에는 대부분의 값이 오버플로우가 되어버리고

현재 float로 했음에도 값이 커지면 오버플로우 에러가 발생하니 아주 미치겠습니다..

확실한 방법 없을까요?

애초에 문제 접근을 잘못한것같기도 한데..

어떻게 접근해야할지 감이 안잡히네요..