问题 H: 利物浦集合

对于 $n,m,k$，一个长度为 $n$ 的整数数列 a1,a2,a3,⋯,ana1,a2,a3,⋯,an 如果满足下面的所有条件，则称它为利物浦集合。

1. 0≤a1≤a2≤a3≤⋯≤an<2m0≤a1≤a2≤a3≤⋯≤an<2m。
2. ⊕i=1nai=0⊕i=1nai=0，其中 $\oplus$ 表示二进制按位异或。
3. 对于所有整数 $i$（$1\le i\le n-k$），ai≠ai+kai=ai+k。

记函数 $f(n,m,k)$ 表示对于 $n,m,k$ 的不同利物浦集合的个数 对 $1000000007$ 取模后的值。

你的目标是计算一些与函数 $f$ 有关的值。具体内容见 输入/输出格式。

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 100$）表示测试数据组数。

对于每一组测试数据，输入包含两行。

第一行包含三个整数 n1,m1,k1n1,m1,k1（1≤n1≤1071≤n1≤107，1≤∑n1≤6×1071≤∑n1≤6×107，1≤m1≤231≤m1≤23，1≤k1≤n11≤k1≤n1）。

第二行包含两个整数 n2,m2n2,m2（1≤n2≤1061≤n2≤106，1≤∑n2≤1071≤∑n2≤107，1≤m2≤231≤m2≤23）。

对于每一组测试数据，输出包含两行。

第一行包含一个整数表示 f (n1,m1,k1)f (n1,m1,k1)。

第二行包含两个整数 $xor,sum$，分别表示所有 f (n2,m2,i)f (n2,m2,i)（1≤i≤n21≤i≤n2）的异或和，和所有 f (n2,m2,i)2f (n2,m2,i)2（1≤i≤n21≤i≤n2）的和对 $1000000007$ 取模后的值。

具体地，$xor,sum$ 满足以下条件：xor=⊕i=1n2f (n2,m2,i)xor=⊕i=1n2f (n2,m2,i)sum=(∑i=1n2f (n2,m2,i)2)mod1000000007sum=(i=1∑n2f (n2,m2,i)2)mod1000000007

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

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

在样例的第一组测试数据的第二问中：

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