本题目满分 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}$。

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