생일 파티

오늘은 상근이의 생일이다. 상근이는 생일 파티에 친구 $f$명을 초대했고, 나눠 줄 사탕 $n$개가 있다. 친구에게는 $1$번부터 $f$번까지 번호가 매겨져 있다.

상근이는 다음 두 규칙을 지키면서 사탕을 나눠 준다.

• 모든 친구는 사탕을 적어도 한 개 받는다.
• $i$번 친구가 받은 사탕의 개수를 $a_i$라고 할 때, 모든 $a_i$를 나누는 $1$보다 큰 양의 정수 $x$가 있으면 안 된다.

$n$과 $f$가 주어지면 사탕을 나눠 주는 방법의 수를 구하는 프로그램을 작성하시오.

어느 친구가 몇 개를 받았는지가 다르면 서로 다른 방법으로 센다. 예를 들어 1번 친구에게 1개, 2번 친구에게 2개를 준 경우와 1번 친구에게 2개, 2번 친구에게 1개를 준 경우는 다른 방법이다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 100000$)가 주어진다.

둘째 줄부터 $T$개의 줄에 각 테스트 케이스의 $n$과 $f$가 공백을 사이에 두고 주어진다. ($1 \le f \le n \le 10000$)

각 테스트 케이스마다 사탕을 나눠 주는 방법의 수를 $1000000007$로 나눈 나머지를 한 줄에 하나씩 출력한다.

$n = 6$, $f = 2$인 경우 가능한 방법은 $[1, 5]$와 $[5, 1]$이다.

$n = 7$, $f = 2$인 경우에는 $[1, 6]$, $[2, 5]$, $[3, 4]$, $[4, 3]$, $[5, 2]$, $[6, 1]$이 가능하다.