G. Binary Function II
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$f(x)$$$ be the number of positive integers $$$y$$$ such that $$$y \lt x$$$ and $$$\text{popcount}(y) \gt \text{popcount}(x)$$$, where $$$\text{popcount}(z)$$$ is equal to the number of $$$1$$$s in the binary representation of $$$z$$$.

Given $$$l$$$, $$$r$$$ $$$(1 \leq l \leq r)$$$ in their binary representation, find $$$\sum_{x=l}^{r} f(x)$$$. Because this number might be too large, output the answer modulo $$$998244353$$$.

Note: $$$|x|$$$ represents the length of $$$x$$$ in its binary representation. Also, some values of $$$x$$$ might be too large to convert to an integer, even with $$$64$$$ bits.

Input

The first and only line of the input contains a value of $$$l$$$ and $$$r$$$ $$$(1 \leq |l| \leq |r| \leq 1000)$$$ separated by a space.

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-2$$$ satisfy $$$|l|, |r| \leq 10$$$.

Tests $$$3-6$$$ satisfy $$$|l|, |r| \leq 100$$$.

Tests $$$7-20$$$ satisfy no additional constraints.

Output

Output the sum of $$$f(x)$$$ across the interval $$$x=l$$$ to $$$x=r$$$ inclusive modulo $$$998244353$$$.

Examples
Input
1000 1111
Output
8
Input
1 101011
Output
184
Input
11010 11001000110
Output
364182
Note

In the first sample, $$$l = 1000$$$ in binary equals $$$8$$$, and $$$r = 1111$$$ in binary equals $$$15$$$. $$$f(8) + f(9) + f(10) + f(11) + f(12) + f(13) + f(14) + f(15) = 4 + 1 + 1 + 0 + 2 + 0 + 0 + 0 = 8$$$.

—

Problem Idea: Mustela_Erminea

Problem Preparation: Mustela_Erminea

Occurrences: Advanced G