수학 문제

팬 $n$명 $F_i$ ($i=1,\cdots,n$)과 팀 $m$개 $T_j$ ($j=1,\cdots,m$)가 있다.

(i) 각 팬 $F_i$는 적어도 한 팀의 팬이지만, 모든 팀의 팬은 아니다.

(ii) 임의의 두 팀 $T_i, T_j$ ($1 ≤ i, j ≤ m$)에 대해, 두 팀 모두의 팬인 팬들의 집합과 정확히 같은 팬 집합을 가진 팀 $T_k$ ($1 ≤ k ≤ m$)가 정확히 하나 있다. $i$, $j$, $k$는 같을 수 있다.

(iii) 임의의 두 팀 $T_i, T_j$ ($1 ≤ i, j ≤ m$)에 대해, 두 팀 중 한 팀 이상의 팬인 팬들의 집합과 정확히 같은 팬 집합을 가진 팀 $T_k$ ($1 ≤ k ≤ m$)가 정확히 하나 있다. $i$, $j$, $k$는 같을 수 있다.

이 조건을 모두 만족하는 팬과 팀의 대응 방식이 몇 가지인지 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($T ≤ 100000$)가 주어진다.

각 테스트 케이스는 한 줄에 정수 $n$, $m$ ($1 ≤ n ≤ 10^{18}$, $2 ≤ m ≤ 6$)이 주어진다.

각 테스트 케이스마다 답을 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.