a.cpp/5s/512MB

Description

只因老师是一名职业撸胖撸选手。今天又是他出去上分的好日子。

今天只因老师只想推图。这个图可以看成一个有$n$个点的无重边，无自环的图，然后还有若干条边。只因老师想着他要从$1$到$n$按顺序去打每个点，每打一个点就会和前面的点发生一些不可描述的关系，这个关系的产生可以参考以下代码。

int n,lim;
int ed[233][233],f[233][233];//一条边(x,y)会使得ed[x][y]=ed[y][x]=1
void work()
{
    lim=n;
    for(int i=1;i<=n;++i)
         for(int j=1;j<=n;++j)
            f[i][j]=ed[i][j];
    for(int o=1;o<=lim;++o)//第o次打的点为o，总共打lim个点(lim一般情况下为n)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                f[i][j]=f[i][j]||(i!=j&&f[i][o]&&f[o][j]);
}

正当只因老师推图的正带劲之时，某督查进来了，只因老师只能推到第$m$个点就连忙停止推图，装作自己在做题。然而队友还在召唤着他，所以只因老师并没有注意督查有没有走，继续开始了推图...

后面发生的事情，我们不得而知。但是，今天只因老师重新找到了你，为了发泄自己心中的不满，他给了你一个问题：给定数$n,m$,问有多少个本质不同的点数为$n$的图，满足这个图在$lim=m$条件下推图后得到的$f$数组 和在$lim=n$条件下推图后得到的$f$数组 完 全 一 致。两个图本质不同当且仅当存在一条边$(x,y)(x\neq y)$在其中一个图中出现并且在另一个图中不出现。你能解决吗？由于答案可能较大，你只要输出答案对$10^9+7$取模的结果即可。

Input

本题有多组测试数据。

第一行为一个数$T$,表示测试数据组数。

后面每行两个非负整数$n,m$,含义见题目描述。

Output

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

Sample

Input

4

4 1

5 4

1 1

3 2

Output

25

814

1

7

Sample Explanation

对于第四组样例，只有当图中出现的边为$\{(1,3),(2,3)\}$的时候，这个图才不合法。

Constraint

对于$0\%$的数据，和样例完全一致。

对于$10\%$的数据，$n\le 7$。

对于$20\%$的数据，$n\le 10$。

对于$30\%$的数据，$n\le 20$。

对于$50\%$的数据，$n\le 50$。

对于另外$10\%$的数据，$m=n$。

对于另外$10\%$的数据，$m=0$。

对于$100\%$的数据，$T\le 11451,1\le n\le 200,0\le m \le n$。