对于 $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$。

1. $\oplus_{i=1}^na_i=0$，其中 $\oplus$ 表示二进制按位异或。
2. 对于所有整数 $i$（$1\le i\le n-k$），$a_i\not=a_{i+k}$。

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

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

本题包含多组测试数据。

首先在第一行输入一个整数 $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$）。

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

第一行包含一个整数表示 $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$。

在样例的第一组测试数据的第一问中，$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$ 满足题意。