A Math Problem

There are $n$ fans $F_i$ ($i=1,\cdots,n$) and $m$ teams $T_j$ ($j=1,\cdots,m$).

(i) Each fan $F_i$ is a fan of at least one team but not a fan of all teams.

(ii) For any two teams $T_i, T_j$ ($1 ≤ i, j ≤ m$), there is exactly one team $T_k$ ($1 ≤ k ≤ m$) whose set of fans is exactly the set of fans shared by $T_i$ and $T_j$. $i$, $j$, and $k$ may be equal.

(iii) For any two teams $T_i, T_j$ ($1 ≤ i, j ≤ m$), there is exactly one team $T_k$ ($1 ≤ k ≤ m$) whose set of fans is exactly the set of fans of $T_i$ or $T_j$. $i$, $j$, and $k$ may be equal.

Count the number of ways to assign fans to teams (the correspondences between fans and teams) that satisfy these conditions.

The first line contains an integer $T$ ($T ≤ 100000$), the number of test cases.

Each test case is a single line with two integers $n$ and $m$ ($1 ≤ n ≤ 10^{18}$, $2 ≤ m ≤ 6$).

For each test case, print the answer modulo $10^9+7$ on its own line.