题目描述

给定整数 $L, R, V$。请你求满足以下两个条件的整数对 $(l, r)$ 的个数，并将结果对 $998244353$ 取模后输出。

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

这里，$\oplus$ 表示按位异或（XOR）运算。

按位异或（XOR）运算是这样定义的：对于非负整数 $A, B$，$A \oplus B$ 的二进制表示中，每一位 $2^k$（$k \geq 0$）上的数，如果 $A$ 和 $B$ 的该位中恰好有一个是 $1$，则结果的该位为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。 一般来说，$k$ 个非负整数 $p_1, p_2, p_3, \dots, p_k$ 的按位异或为 $(\dots((p\_1 \oplus p\_2) \oplus p\_3) \oplus \dots \oplus p\_k)$，并且可以证明，这个结果与 $p_1, p_2, \dots, p_k$ 的顺序无关。

输入格式

输入从标准输入读取，格式如下：

$L$ $R$ $V$

输出格式

输出答案。

样例 1

输入

1 3 3

输出

2

样例 2

输入

10 20 0

输出

6

样例 3

输入

1 1 1

输出

1

样例 4

输入

12345 56789 34567

输出

16950

说明/提示

限制

• $1 \leq L \leq R \leq 10^{18}$
• $0 \leq V \leq 10^{18}$
• 输入的所有值均为整数

样例解释 1

满足条件的有 $(l, r) = (1, 2)$ 和 $(l, r) = (3, 3)$，共 $2$ 个。

由 ChatGPT 4.1 翻译