利物浦集合

Problem Description

对于 $n,m,k$，一个长度为 $n$ 的整数数列 $a_1,a_2,a_3,\cdots,a_n$ 如果满足下面的所有条件，则称它为利物浦集合。

1. $0\le a_1\le a_2\le a_3\le\cdots\le a_n\lt 2^m$。
2. $\oplus_{i=1}^na_i=0$，其中 $\oplus$ 表示二进制按位异或。
3. 对于所有整数 $i$（$1\le i\le n-k$），$a_i\not=a_{i+k}$。 记函数 $f\ (n,m,k)$ 表示对于 $n,m,k$ 的不同利物浦集合的个数 对 $1000000007$ 取模后的值 。 你的目标是计算一些与函数 $f$ 有关的值。具体内容见 输入/输出格式。

Input

本题包含多组测试数据。 首先在第一行输入一个整数 $T$（$1\le T\le100$）表示测试数据组数。 对于每一组测试数据，输入包含两行。 第一行包含三个整数 $n_1,m_1,k_1$（$1\le n_1\le 10^7$，$1\le \sum n_1\le 6\times 10^7$，$1\le m_1\le23$，$1\le k_1\le n_1$）。 第二行包含两个整数 $n_2,m_2$（$1\le n_2\le10^6$，$1\le \sum n_2\le 10^7$，$1\le m_2\le23$）。

Output

对于每一组测试数据，输出包含两行。 第一行包含一个整数表示 $f\ (n_1,m_1,k_1)$。 第二行包含两个整数 $xor,sum$，分别表示所有 $f\ (n_2,m_2,i)$（$1\le i\le n_2$）的异或和，和所有 $f\ (n_2,m_2,i)^2$（$1\le i\le n_2$）的和对 $1000000007$ 取模后的值。 具体地，$xor,sum$ 满足以下条件：

$$xor=\oplus_{i=1}^{n_2}f\ (n_2,m_2,i)$$ $$sum=(\sum_{i=1}^{n_2}f\ (n_2,m_2,i)^2)\bmod 1000000007 $$

其中 $\oplus$ 表示二进制按位异或，$\bmod$ 表示取模，例如 $3\bmod 2=1,(-7)\bmod 3=2$。

Sample Input

4
2 2 1
3 2
3 4 2
2 3
4 3 2
1 1
99999 23 10000
100000 22

Sample Output

0
0 42
50
8 64
42
1 1
125954947
904110746 926732671

Hint

在样例的第一组测试数据的第一问中，$f\ (2,2,1)=0$，因为不存在任何一个序列满足条件。 在样例的第一组测试数据的第二问中：

1. $f\ (3,2,1)=1$，即序列 $a_1=1,a_2=2,a_3=3$ 满足题意。
2. $f\ (3,2,2)=f\ (3,2,1)+3$，即对于整数 $i$（$1\le i\le 3$），序列 $a_1=0,a_2=a_3=i$ 满足题意。
3. $f\ (3,2,3)=f\ (3,2,2)+1$，即序列 $a_1=a_2=a_3=0$ 满足题意。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（4）