問題文

整数 $L,R,V$ が与えられます． 次の条件を両方満たす整数の組 $(l,r)$ の個数を $998244353$ で割った余りを求めてください．

• $L \\leq l \\leq r \\leq R$
• $l \\oplus (l+1) \\oplus \\cdots \\oplus r=V$

ただしここで，$\\oplus$ はビット単位 $\\mathrm{XOR}$ 演算を表します．

ビット単位 $\\mathrm{XOR}$ 演算とは

非負整数 $A, B$ のビット単位 $\\mathrm{XOR}$ 、$A \\oplus B$ は、以下のように定義されます。

• $A \\oplus B$ を二進表記した際の $2^k$ ($k \\geq 0$) の位の数は、$A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。

例えば、$3 \\oplus 5 = 6$ となります (二進表記すると: $011 \\oplus 101 = 110$)。
一般に $k$ 個の非負整数 $p_1, p_2, p_3, \\dots, p_k$ のビット単位 $\\mathrm{XOR}$ は $(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$ と定義され、これは $p_1, p_2, p_3, \\dots p_k$ の順番によらないことが証明できます。

制約

• $1 \\leq L \\leq R \\leq 10^{18}$
• $0 \\leq V \\leq 10^{18}$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

$L$ $R$ $V$

出力

答えを出力せよ．

入力例 1

1 3 3

出力例 1

2

条件を満たすのは，$(l,r)=(1,2)$ と $(l,r)=(3,3)$ の $2$ つです．

入力例 2

10 20 0

出力例 2

6

入力例 3

1 1 1

出力例 3

1

入力例 4

12345 56789 34567

出力例 4

16950