题目描述

你正在订购一个蛋糕来庆祝新年。你需要确定装饰物品在蛋糕上的数量。可用的物品有狗雕像、猫雕像、红色糖果和蓝色糖果。

你希望用这四种物品装饰蛋糕，并且这四种物品的数量彼此不同。你还希望雕像（狗和猫的总数）的数量在某个范围内。

装饰物品的额外费用会加到蛋糕的价格中。额外费用虽然相当奇怪，但却是四种装饰物品数量的乘积。你希望在预算允许的情况下，让蛋糕看起来尽可能华丽。因此，如果你可以在不违反预算限制的情况下增加四种物品中的任意一种，那么你对这种装饰方案就不满意。

上述条件总结如下：设 $d$、$c$、$r$ 和 $b$ 分别表示狗雕像、猫雕像、红色糖果和蓝色糖果的数量。所有这些数量应是不同的正整数，并满足给定的 $X$、$L$ 和 $R$ 的以下条件：

• $L \leq d + c < R$，
• $d \times c \times r \times b \leq 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$，以及
• $d \times c \times r \times (b+1) > X$。

可能有多种装饰物品数量的组合满足这些条件。你的任务是找出有多少种这样的组合存在。

输入格式

输入由单个测试用例组成，格式如下。

这里，$X$、$L$ 和 $R$ 是上述条件中出现的整数。它们满足 $1 \leq X \leq 10^{14}$ 和 $1 \leq L < R \leq 10^{14}$。

输出格式

输出满足上述条件的装饰物品数量组合的数量，结果对质数 $998244353 = 2^{23} \times 7 \times 17 + 1$ 取模。

24 4 6

12

30 5 6

4

30 9 20

0

100000000000000 1 100000000000000

288287412

提示

对于样例输入 2，四种组合 $(d, c, r, b) = (2,3,1,5)$、$(2,3,5,1)$、$(3,2,1,5)$ 和 $(3,2,5,1)$ 满足所有条件。$(d, c, r, b) = (1,4,2,3)$ 不符合条件，因为即使再增加一只猫雕像，其装饰物品的额外费用也没有超过 $X = 30$。$(d, c, r, b) = (1,5,2,3)$ 也不符合条件，因为 $d + c < R = 6$ 不成立。