13534번 - 생일 파티

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

상근이는 다음과 같은 규칙을 지키면서 친구들에게 사탕을 나눠주려고 한다.

• 모든 사람은 사탕을 적어도 1개 받아야 한다.
• i번째 사람이 받은 사탕의 개수를 a_i라고 했을 때, 모든 a_i를 나누는 양의 정수 x > 1이 존재하면 안 된다.

n과 f가 주어졌을 때, 사탕을 나눠줄 수 있는 방법의 수를 구하는 프로그램을 작성하시오.

사탕을 나눠주는 순서가 다르면 다른 방법으로 친다. 예를 들어, 1번 친구에게 1개, 2번 친구에게 2개를 나눠준 것과 1번 친구에게 2개, 2번 친구에게 1개를 나눠준 것은 다른 경우이다.

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100,000)가 주어진다.

둘째 줄부터 T개의 줄에 n과 f가 주어진다. (1 ≤ f ≤ n ≤ 10,000)

각각의 테스트 케이스마다 사탕을 나눠주는 방법을 1,000,000,007로 나눈 나머지를 출력한다.

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

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