该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

$\hspace{15pt}$困扰学长们的气球的问题终于解决了，学长们为这次校赛购买了足够的气球。但随之而来的，是为校赛的题目怎么出，这可把学长们难住了。

$\hspace{15pt}$已知这次校赛共有 $n$ 道题，且至多涉及 $m$ 个知识点。学长们讨论了知识点分配问题后决定：

$\hspace{15pt}$ 1.不应该有某道题涉及全部的知识点

$\hspace{15pt}$ 2.不应该有某道题不涉及任何知识点

$\hspace{15pt}$ 3.可以有知识点不被任何题目涉及

$\hspace{15pt}$请你帮学长们算出共有多少种分配方案。由于结果可能过大，请对 $10^9 + 7$ 取模后输出结果。 请注意，一道题可以涉及多个知识点，一个知识点可以被多个题涉及。

Format

Input

$\hspace{15pt}$第一行输入一个正整数 $t\space (1\leq t \leq 100)$ 表示 $t$ 组输入。

$\hspace{15pt}$接下来 $t$ 行，每行两个整数 $n,\,m\space (1\leq n,\,m\leq 10^6)$ 分别代表题目数量和知识点数量。

Output

$\hspace{15pt}$输出共 $t$ 行，每行一个整数表示合法的分配方案数，结果需要对 $10^9+7$ 取模。

Samples

3
1 3
3 6
100 100

6
238328
930270576