Description

「那么，你相信宿命吗？」

“那种东西，顶多只是什么励志故事里的抒情工具吧。”

「是吗… 那么要玩玩塔罗牌吗？」

“谁会对那种事情感兴趣…”

「真是的，你要再一副对什么事情都漠不关心的态度我要生气了…！」

“好好好… 所以呢？塔罗牌呢？”

「这个嘛… 嘿嘿，自己想象咯～」

“什么毛病…”

「现在有 $n$ 叠塔罗牌放在桌上，每一叠都有 $2^n$ 张，从桌面向上分别是 $1$ 号、$2$ 号… $n$ 号。现在作为宿命的管理者的我们——要洗一遍这些塔罗牌！」

“怎么… 中二病开始传染了吗…”

「那么，洗牌的过程是，将牌均匀地分成两半，下面一半和上面一半分别放在左右手；接着，右手从底部放下一张牌，左手从底部放下一张牌，右手又从底部放下一张牌… 这样交错重复，于是一次洗牌就完成了！」

“例如 $n=2$ 时，假设原来的牌从下往上看是 $[1,2,3,4]$，洗一次牌后就会变成 $[3,1,4,2]$——是这样吗？”

「是的！然后对于这 $n$ 叠初始时都按顺序从下到上摆放的塔罗牌，我会不操作第一叠牌，然后洗一次第二叠牌，洗两次第三叠牌… 洗 $n-1$ 次第 $n$ 叠牌。接下来，我会把这 $n$ 叠牌都从下到上地发给 $2^n$ 个人——也就是说第一个人会拿到每叠牌的第一张，第二个人会拿到每叠牌的第二张… 每一个人都恰好会拿到 $n$ 张牌。」

「现在，定义一个人拿到和自己号码相同的牌的张数为这个人的幸运值。你能算出这 $n$ 个人幸运值的总和是多少吗？」

“嗯… 撇开你粗制滥造的题面不谈，这个题目还是很有趣的。”

「适可而止啊喂！」

“… 我想了想，好像还挺简单的。不妨让我们记 $n=k$ 的时候的幸运值总和为 $f(k)$。现在你需要对 $l\le k\le r$ 的 $f(k)$ 求和，你看怎么样？”

「… 不是很会了…」

简要题意

对于长度为 $2k$ 的序列 $a$，定义函数 $S_q(a)$，其中

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

现在给定正整数 $l,r$，求 $\sum_{k=l}^r f(k)$，其中

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

一行两个正整数 $l,r$，代表求和的起始和终点。

Output Format

输出一行一个正整数，代表 $\sum_{k=l}^rf(k)$。答案对 $998244353$ 取模。

2 2

4

3 4

26

10 20

2096384

Hint

样例解释

以样例一中计算 $f(2)$ 为例。最初有 $2$ 叠牌，从下到上的牌都是 $[1,2,3,4]$。然后现在对第一叠牌不操作，第二叠牌洗一次，于是第二叠牌从下到上变成了 $[3,1,4,2]$。现在把两叠牌发给 $4$ 个人。第一个人拿到 $[1,3]$，第二个人拿到 $[2,1]$，第三个人拿到 $[3,4]$，第四个人拿到 $[4,2]$。发现每个人的幸运值都为 $1$（都恰好拿到了一张和自己号码相同的牌），于是幸运值总和就是 $4$，继而 $f(2)=4$。

数据范围

对于全部数据，有 $1\le l\le r\le 10^{10}$。

Subtask 1（10 pts）：保证 $l=r$ 且 $r\le 12$。

Subtask 2（35 pts）：保证 $l=r$。

Subtask 3（15 pts）：保证 $1\le l\le r\le 10^6$。

Subtask 4（40 pts）：无特殊限制。