有 $n$ 个粉丝 $F_i (i = 1, \dots, n)$ 和 $m$ 个队伍 $T_j (j = 1, \dots, m)$。

(i) 对于任意粉丝 $F_i$，$F_i$ 至少是一个队伍的粉丝，但不是所有队伍的粉丝。

(ii) 对于任意两个队伍 $T_i, T_j (1 \le i, j \le m)$，存在唯一一个队伍 $T_k (1 \le k \le m)$，其粉丝恰好是 $T_i$ 和 $T_j$ 的粉丝的交集。注意 $i, j, k$ 可以相同。

(iii) 对于任意两个队伍 $T_i, T_j (1 \le i, j \le m)$，存在唯一一个队伍 $T_k (1 \le k \le m)$，其粉丝恰好是 $T_i$ 和 $T_j$ 的粉丝的并集。注意 $i, j, k$ 可以相同。

请计算粉丝与队伍之间有多少种对应关系。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T (T \le 100000)$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n, m (1 \le n \le 10^{18}, 2 \le m \le 6)$。

输出格式

对于每组测试数据，输出一个整数，表示答案对 $1000000007 (10^9 + 7)$ 取模的结果。

样例

输入 1

9
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6

输出 1

2
12
36
216
1032
7200
46800
453600
3369600