Problem Description

There are $n$ people, numbered from $1$ to $n$, sitting in a circle playing Josephus.

They count cyclically from $1$ to $m$. Unlike the standard Josephus problem, everyone who does not count to $1$ will be eliminated, until only one person survives.

Let the survivor's number be $x$. Define $J_m(n)=x$.

Given $m,l,r$, compute $\sum_{i=l}^{r} J_m(i)$, and output the result modulo $998244353$.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case:

One line contains three integers $m,l,r$ in order.

Output Format

For each test case:

Output one line with one integer, the result modulo $998244353$.

4
2 1 4
3 3 7
8 12 64
2 1 1048976

6
17
1149
148359175

Hint

This problem uses bundled testcases.

• Subtask 1 (4 pts): $T=1$, $m \leq 10$, $r \leq 200$.
• Subtask 2 (8 pts): $T=1$, $m \leq 10^6$, $r \leq 10^7$.
• Subtask 3 (8 pts): $\sum (r-l+1) \leq 2 \times 10^6$.
• Subtask 4 (10 pts): $m=2$.
• Subtask 5 (25 pts): $T \leq 5$, $m \leq 10^6$.
• Subtask 6 (45 pts): No special constraints.

For $100\%$ of the testdata, $1 \leq T \leq 10^4$, $2 \leq m \leq 10^{12}$, $1 \leq l \leq r \leq 10^{18}$.

Translated by ChatGPT 5