【提高】划分数

给你一个正整数 $n$，将 $n$ 划分成若干个正整数的和的方案数，称为 $n$ 的 划分数。

比如：$n = 6$ 的划分数为 $11$

$$\begin{aligned} &6 \\=& 6 \\=& 1 + 5 \\=& 2 + 4 \\=& 3 + 3 \\=& 1 + 1 + 4 \\=& 1 + 2 + 3 \\=& 2 + 2 + 2 \\=& 1 + 1 + 1 + 3 \\=& 1 + 1 + 2 + 2 \\=& 1 + 1 + 1 + 1 + 2 \\=& 1 + 1 + 1 + 1 + 1 + 1 \end{aligned}$$

请注意：$1+1+4$ 和 $1+4+1$ 是同一种方案

在这 $11$ 种方案中，如果要求划分出来的数 $x_i$ 满足 $1 \le x_i \le 2$，就只有 $4$ 种方案：

$$\begin{aligned} &6 \\=& 6 \\=& 2 + 2 + 2 \\=& 1 + 1 + 2 + 2 \\=& 1 + 1 + 1 + 1 + 2 \\=& 1 + 1 + 1 + 1 + 1 + 1 \end{aligned}$$

这个问题常见的问法还有：$n$ 个 相同的小球，放到 $m$ 个 相同的盒子 里，盒子不能为空 的方案数。

上面的问题等价于：将 $n$ 划分成恰好 $m$ 个数的和的方案数

输入格式

一行 $3$ 个整数 $n, l, r$

输出格式

对于每组数据输出一行，表示将 $n$ 划分成 $[l, r] 中的数的和的划分数$，答案对 998244353 取模

6 1 6

11

6 1 2

4

提示

【样例 1 解释】

【数据范围】

• subtask-1（10 pt）：保证 $n \le 10^3, l=1, r=n$
• subtask-2（20 pt）：保证 $n \le 10^3$
• subtask-3（30 pt）：保证 $n \le 5 \times 10^5, l =1, r = n$
• subtask-4（40 pt）：无特殊限制
• 保证 $1 \le l \le r \le n, 1 \le n \le 5 \times 10^5$

请思考后再点击查看提示

来源

• 核桃070，CSP-S，T4：附魔