Problem Background

"Seeing the next part of the dream"...?

"Yes... 'Even though the body is an adult, the heart remains that unrealistic child, the one who believes in endless possibilities—even after recognizing the gap between reality and ideals, still remains so. The dream of becoming a rock star in youth now seems exceptionally unattainable, only visible in glimpses as I move forward'... Doesn't the author sound like me?"

"Once, the young me was filled with curiosity and joy for all the unknowns, but now it feels like I'm just clutching at my dreams that stray from reality, gradually seeing the next part of the dream in the currents of life... Knowing my own failures, yet still climbing up as if to see or achieve something, in this way, I'm no different from the 'active loser' described by the author..."

"So, what exactly do you expect to see or achieve?"

"...I don't know anymore."

Problem Description

"Do you believe in fate?"

"That stuff is just a lyrical tool in some inspirational stories."

"Really... How about a game of tarot cards?"

"Who would be interested in that..."

"Seriously, if you keep this indifferent attitude towards everything, I'm going to get angry...!"

"Alright, alright... So, tarot cards?"

"Well... hehe, imagine it yourself~"

"What's wrong with you..."

"Now there are $n$ stacks of tarot cards on the table, each stack has $2^n$ cards, numbered from bottom to top as 1, 2... $n$. As the managers of fate, we need to shuffle these tarot cards!"

"How... is the middle school syndrome spreading..."

"The process of shuffling is to evenly split the cards into two halves, with the lower half in the left hand and the upper half in the right hand; then, the right hand places one card from the bottom, followed by the left hand placing one card from the bottom, then the right hand again... This alternates repeatedly, completing one shuffle!"

"For example, when $n=2$, if the original cards from bottom to top are $[1,2,3,4]$, after one shuffle, it becomes $[3,1,4,2]$—is that right?"

"Yes! Then for these $n$ stacks of cards initially arranged in order from bottom to top, I will not operate on the first stack, shuffle the second stack once, shuffle the third stack twice... shuffle the $n$-th stack $n-1$ times. Next, I will distribute these $n$ stacks of cards from bottom to top to $2^n$ people—that is, the first person will get the first card from each stack, the second person will get the second card from each stack... Each person will exactly receive $n$ cards."

"Now, define the number of cards a person receives that match their number as the person's luck value. Can you calculate the total luck value of these $n$ people?"

"Hmm... Setting aside your poorly crafted problem statement, the problem itself is quite interesting."

"Enough already!"

"I've thought about it, and it seems quite simple. Let's denote the total luck value when $n=k$ as $f(k)$. Now you need to sum $f(k)$ for $l \leq k \leq r$, how does that sound?"

"...I'm not sure..."

Brief Problem Statement

For a sequence $a$ of length $2k$, define the function $S_q(a)$, where

$$ S_q(a)= \begin{cases} a, & q=0 \\ [a_{k+1}, a_1, a_{k+2}, a_2, \dots, a_{2k}, a_k], & q=1 \\ S_{q-1}(S_1(a)), & \text{otherwise.} \end{cases} $$

Given positive integers $l, r$, find $\sum_{k=l}^r f(k)$, where

$$ f(n)=\sum_{q=0}^{n-1}\sum_{k=1}^{2^n}\left[S_q([1,2,3,\dots,2^n])_k=k\right] $$

Input and Output Formats

Input Format

One line with two positive integers $l, r$, representing the start and end of the summation.

Output Format

Output one line with a positive integer, representing $\sum_{k=l}^r f(k)$. The answer should be modulo $998244353$.

Sample Input and Output

Sample Input #1

2 2

Sample Output #1

4

Sample Input #2

3 4

Sample Output #2

26

Sample Input #3

10 20

Sample Output #3

2096384

Notes

Sample Explanation

Taking the calculation of $f(2)$ in Sample 1 as an example. Initially, there are 2 stacks of cards, both from bottom to top being $[1,2,3,4]$. Then, no operation is performed on the first stack, and the second stack is shuffled once, so the second stack from bottom to top becomes $[3,1,4,2]$. Now, distribute the two stacks to 4 people. The first person gets $[1,3]$, the second person gets $[2,1]$, the third person gets $[3,4]$, and the fourth person gets $[4,2]$. It is found that everyone's luck value is 1 (each person exactly receives one card matching their number), so the total luck value is 4, hence $f(2)=4$.

Data Range

For all data, $1 \leq l \leq r \leq 10^{10}$.

Subtask 1 (10 pts): Guaranteed $l=r$ and $r \leq 12$.

Subtask 2 (35 pts): Guaranteed $l=r$.

Subtask 3 (15 pts): Guaranteed $1 \leq l \leq r \leq 10^6$.

Subtask 4 (40 pts): No special restrictions.

见题面 Input 部分

见题面 Output 部分