안전한 레이스

내일은 레이스 날이다. 트랙 옆에는 깃발로 드라이버에게 신호를 보내는 트랙 마셜이 서 있다. 노란 깃발은 위험을 알리고, 파란 깃발은 한 바퀴 뒤진 차에게 더 빠른 차에게 길을 비켜 주라고 지시한다. 마셜은 각자 마셜 부스에서 근무한다. 마셜 부스는 트랙에서 잘 보이는 보호용 우리다.

트랙은 원형이고 길이는 $L$데카미터다. 부스는 10미터(1데카미터)마다 하나씩 있어서 정확히 $L$개이고, 출발점에서 $0, 1, \dots, L-1$데카미터 지점에 놓여 있다.

부스를 모두 쓸 필요는 없다. 규정은 연속한 두 마셜 사이의 거리를 최대 $S$데카미터로 제한한다. 즉 원을 따라 연속한 부스 $S$개를 어떻게 잡아도 그 안에 마셜이 최소 한 명 있어야 한다. 마셜은 결승 깃발을 흔들지 않으므로 출발점 겸 결승점 부스에 마셜을 두는 것은 의무가 아니고 금지도 아니다.

규정을 만족하는 마셜 배치의 개수를 $123456789$로 나눈 나머지를 구하라.

두 정수 $L$과 $S$가 주어진다. $L$은 트랙의 길이, $S$는 연속한 두 마셜 사이의 최대 거리다. ($1 \le S \le L \le 10^6$)

규정을 만족하는 배치의 개수 $W$를 $123456789$로 나눈 나머지를 한 줄에 출력한다. 출력하는 값은 $0 \le W < 123456789$를 만족한다.

$L = 3$, $S = 2$일 때 유효한 배치는 네 가지다. 출발점에서 0과 1데카미터 지점, 0과 2데카미터 지점, 1과 2데카미터 지점, 그리고 0과 1과 2데카미터 지점에 마셜을 두는 배치다.