P8181 "EZEC-11" Circle

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$.

**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.

For each test case: Output one line with one integer, the result modulo $998244353$.

**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