13471번 - Safe Racing 다국어

Tomorrow is racing day. There will be yet another grand prix in yet another country. Beside the safety car, there are various other security measures in order to make sure that everybody is as safe as possible. Among these safety measures are the track marshals: special race officials standing along the track with an assortment of flags that they can use to signal various messages to the drivers. For instance, the yellow flag warns the drivers of a dangerous situation, and the blue flag is used to order a lapped car to make way for one of the faster cars.

Every marshal should be stationed in a so-called marshal booth, a kind of protected cage that is clearly visible from the race track. These booths are located at regular intervals of ten metres (one decametre) along the track. The track is circular and L decametres long and therefore contains exactly L booths.

Not every booth needs to be used. International racing regulations require that the distance between two consecutive marshals should be at most S decametres, meaning that every S consecutive booths should contain at least one marshal. The marshals are not responsible for waving the finish flag, so it is not required (but also not forbidden) to have a marshal at the start/finish.

This leaves you with many ways of assigning marshals to the various booths along the track. Out of sheer curiosity you decide to calculate the total number of valid marshal assignments. Reduce your answer modulo 123 456 789 in case it gets too large.

The input consists of two integers L, the length of the track, and S, the maximal distance between consecutive marshals along the track, satisfying 1 ≤ S ≤ L ≤ 10⁶.

Output the integer W, the number of ways to put marshals modulo 123 456 789. (Your answer must satisfy 0 ≤ W < 123 456 789.)

In the first sample test case, the four solutions are to put marshals at distances 0 and 1, at distances 0 and 2, at distances 1 and 2, or, at distances 0, 1 and 2 (in decametres) from the start.