题目描述

小虾被定为了春游活动的组织员，他需要从班里选出一些人进行合作。

具体地，小虾的班里每个人的编号为一个非负整数（可以很大），每个非负整数对应恰好一个同学。每次他会选两名同学，假设这两名同学的编号分别为 $x$ 和 $y$。如果 $x,y$ 满足 $l\leq ((x\&y)+(x|y))\leq r$，则称这两名同学相配。

注： $\&,|$ 分别为 按位与 和 按位或。如果对这个不清楚，可以查看下方的提示说明部分。

小虾想问你，问有多少对相配的同学（顺序不同算两种，$x,y$ 可以相同）？

输入格式

共一行，两个非负整数 $l,r$。

输出格式

共一行，一个非负整数 $ans$，表示答案对于 $998244353$ 取模的结果。

样例 1

输入

1 1

输出

2

解释

一组满足条件的 $x$ 和 $y$ 分别为 $1$ 与 $0$。

计算可得 $(x\&y)=0$，继续计算得到 $(x|y)=1$，所以 $(x\&y)+(x|y)=1$，满足条件。

另一组满足条件的 $x$ 与 $y$ 即为上文的 $x$ 与 $y$ 交换。

样例 2

输入

114 191

输出

11973

样例 3

该样例符合测试点 $7\sim 10$ 的限制。

输入

见下发文件中的prilov3.in

输出

见下发文件中的 prilov.out

样例 4

该样例符合测试点 $11\sim 12$ 的限制。

输入

见下发文件中的 prilov\prilov4.in

输出

见下发文件中的 prilov\prilov4.out

数据范围与提示

数据编号	特殊性质
$1\sim 2$	$l,r\leqslant 4$
$3\sim 4$	$l,r\leqslant 8$
$5\sim 6$	$l=r$
$7\sim 10$	$l,r\leqslant 1000$
$11\sim 12$	$l,r\leqslant 10^9$
$13\sim 20$	无特殊性质

对于 $100\%$ 的数据，满足 $0\leqslant l\leqslant r\leqslant 10^{18}$

关于位运算

求一个数 $a$ 的二进制，即 $(a)_2$，可以通过以下 C++ 代码获取。

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int x;
string fun(int x)
{
	string result="";
	for(int i=30;i>=0;i--)
	{
		int w=1;
		for(int j=1;j<=i;j++)
		 w*=2;
		if(x>=w)
		{
			x-=w;
			result="1"+result;
		}
		else
		{
			result="0"+result;
		}
	}
	return result;
}
int main()
{
	cin>>x;
	cout<<fun(x)<<endl;
}

即通过贪心获取。$(a\&b)$ 的结果的某一位是 $1$ 仅当 $a$ 和 $b$ 的这一位上都为 $1$，否则为 $0$。$(a|b)$ 的结果的某一位是 $0$ 仅当 $a$ 和 $b$ 的这一位上都为 $0$，否则为 $1$。

下面这个代码会分别输出 $(a\&b)$ 和 $(a|b)$ 二进制下的结果。

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int a,b;
string fun(int a)
{
	string result="";
	for(int i=30;i>=0;i--)
	{
		int w=1;
		for(int j=1;j<=i;j++)
		 w*=2;
		if(a>=w)
		{
			a-=w;
			result="1"+result;
		}
		else
		{
			result="0"+result;
		}
	}
	return result;
}
int main()
{
	cin>>a>>b;
	cout<<fun(a&b)<<endl<<fun(a|b)<<endl;
}