You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

本题目满分 150 分。

题目名称来自 はぐ (feat. 初音ミク & 可不) 的歌词。

题目描述

MIMI 给了你四个非负整数 $N,L,R,K$，问有多少个长为 $N$ 的序列 $a$ 满足：

• $L\le a_i\le R$
• $a_1\text{ xor }a_2\text{ xor }\cdots\text{ xor }a_N=K$。

答案对 $998244353$ 取模。两个长为 $N$ 的序列 $a,b$ 不同，当且仅当存在 $1\le i\le N$ 使得 $a_i\neq b_i$。

输入格式

本题有多组数据。 第一行一个正整数 $T$ 表示数据组数。

对于每组数据会输入一行四个非负整数 $N,L,R,K$。

输出格式

对于每组数据，输出一行一个非负整数表示符合条件的序列个数对 $998244353$ 取模的值。

样例 $1$ 输入

4
3 1 3 0
4 2 3 1
4 1 3 0
4 0 2 3

样例 $1$ 输出

6
8
21
20

样例 $1$ 说明

对于第一组数据，符合条件的 $a$ 序列有且仅有 $(1,2,3)$ 的 $6$ 种不同排列。

对于第二组数据，符合条件的序列 $a$ 有且仅有 $(2,2,2,3)$ 的 $4$ 种不同排列与 $(2,3,3,3)$ 的 $4$ 种不同排列，因此答案为 $4+4=8$。

样例 $2$

见附加文件。

测试点约束

对于 $100\%$ 的数据，$1\le T\le 10^4,0\le L\le R<2^{60},0\le K<2^{60},1\le N\le 10^{18}$。

每个测试点的详细约束见下表：