题目描述

给定整数 $L$，$R$ 和 $V$。求满足以下两个条件的整数对 $(l,r)$ 的数量（模 $998244353$）。

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

这里，$\\oplus$ 表示按位异或操作。

什么是按位异或？

非负整数 $A$ 和 $B$ 的按位异或，$A \\oplus B$，定义如下：

• 当以二进制写出 $A \\oplus B$ 时，如果 $A$ 和 $B$ 中恰好有一个为 $1$，则在 $2^k$ 位（$k \\geq 0$）上的数字为 $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, 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

10 20 0

示例输出2

6

示例输入3

1 1 1

示例输出3

1

示例输入4

12345 56789 34567

示例输出4

16950