27423번 - Cake Decoration 다국어

You are ordering a cake to celebrate the New Year. You have to decide the numbers of decoration items to be topped on the cake. Available items are dog figures, cat figures, red candies, and blue candies.

You want all four items to decorate the cake, and all the numbers of the four items to be different from each other. You also want the number of figures (the sum of dogs and cats) to be within a certain range.

An extra charge for the decoration items is added to the price of the cake. The extra is, although quite queer, the product of the numbers of the four decoration items. You want the cake to look gorgeous as far as the budget allows. Thus, you are not satisfied with a decoration if you can add any of the four items without violating the budget constraint.

The conditions stated above are summarized as follows. Let $d$, $c$, $r$, and $b$ be the numbers of dog figures, cat figures, red candies, and blue candies, respectively. All these numbers should be different positive integers satisfying the following conditions for given $X$, $L$, and $R$:

• $L ≤ d + c < R$,
• $d \times c \times r \times b ≤ X$,
• $(d + 1) \times c \times r \times b > X$,
• $d \times (c + 1) \times r \times b > X$,
• $d \times c \times (r + 1) \times b > X$, and
• $d \times c \times r \times (b + 1) > X$.

More than one combination of four numbers of decoration items may satisfy the conditions. Your task is to find how many such combinations exist.

The input consists of a single test case of the following format.

$X$ $L$ $R$

Here, $X$, $L$, and $R$ are integers appearing in the conditions stated above. They satisfy $1 ≤ X ≤ 10^{14}$ and $1 ≤ L < R ≤ 10^{14}$.

Output the number of combinations of four numbers of decoration items that satisfy the conditions stated above modulo a prime number $998\,244\,353 = 2^{23} \times 7 \times 17 + 1$.

For Sample Input 2, four combinations of $(d, c, r, b) = (2, 3, 1, 5), (2, 3, 5, 1), (3, 2, 1, 5)$, and $(3, 2, 5, 1)$ satisfy all the conditions. $(d, c, r, b) = (1, 4, 2, 3)$ is not eligible because its extra cost for the decoration items does not exceed $X = 30$ even after adding one more cat figure. $(d, c, r, b) = (1, 5, 2, 3)$ is also ineligible because $d + c < R = 6$ does not hold.