Safe Racing

Time limit2sMemory limit512 MB

Summary

Count binary circular arrangements of L booths where every S consecutive booths contain at least one marshal, modulo 123456789.

Level: Medium6 of 10
Topics: Combinatorics, Dynamic programming, Sliding window
Solved: No attempts yet

Problem

Tomorrow is race day. Track marshals stand along the circuit with flags they use to signal the drivers: a yellow flag warns of danger, and a blue flag orders a lapped car to let a faster car through. Each marshal works from a marshal booth, a protected cage that is clearly visible from the track.

The track is circular and $L$ decametres long. A booth sits every ten metres (one decametre), so there are exactly $L$ booths, at distances $0, 1, \dots, L-1$ decametres from the start.

Not every booth has to be used. The regulations cap the distance between two consecutive marshals at $S$ decametres, which means that any $S$ booths that are consecutive around the circle must contain at least one marshal. Marshals do not wave the finish flag, so a marshal at the start/finish booth is neither required nor forbidden.

Count the marshal assignments that satisfy the regulation and report the count modulo $123456789$ .

Input

The input contains two integers $L$ and $S$ , the length of the track and the maximal distance between consecutive marshals ( $1 \le S \le L \le 10^6$ ).

Output

Print on one line the number $W$ of valid assignments modulo $123456789$ . The printed value satisfies $0 \le W < 123456789$ .

Hint

For $L = 3$ and $S = 2$ there are four valid assignments: marshals at 0 and 1 decametres from the start, at 0 and 2, at 1 and 2, or at 0, 1 and 2.

Examples2

Example 1
Input
```
3 2
```
Expected output
```
4
```
Example 2
Input
```
2500 2000
```
Expected output
```
27511813
```