题目描述

给定两个正整数 $n,k$。

定义集合：

你需要统计满足下列条件的函数 $f(x)$ 的数量：

1. $f:M\to M$。

2. 对任意 $x\in M$，都有：

其中：

并且：

也就是说，$f_k(x)$ 表示对 $x$ 连续作用 $k$ 次函数 $f$ 后得到的结果。

3. 对任意 $x\in M$，都有：

请输出满足条件的函数数量对 $1000000007$ 取模后的结果。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行包含两个整数 $n,k$，其中：

• $n$ 表示集合 $M$ 的上界；
• $k$ 表示函数迭代次数。

输出格式

对于每组测试数据，输出一行一个整数，表示答案对 $1000000007$ 取模后的结果。

数据范围

所有测试数据的 $n\times k$ 之和不超过：

样例输入

7
1 1
2 1
100 1
1 2
2 2
3 2
20 4

样例输出

1
1
1
0
2
0
1048576

提示

当 $k=1$ 时，唯一合法函数是：

当 $n=k=2$ 时，存在两个合法函数：

或：