Birthday Party

Time limit5sMemory limit512 MB

Summary

Count ordered tuples of f positive integers summing to n whose greatest common divisor is 1, modulo 1e9+7, for up to 100000 queries.

Level: Medium7 of 10
Topics: Dynamic programming, Number theory, Combinatorics, Math
Solved: No attempts yet

Problem

Today is Sanggeun's birthday. He invited $f$ friends to the party and has $n$ candies to hand out. The friends are numbered from $1$ to $f$ .

Sanggeun hands out the candies under these two rules.

Every friend receives at least one candy.
Let $a_i$ be the number of candies friend $i$ receives. There must be no positive integer $x > 1$ that divides every $a_i$ .

Given $n$ and $f$ , write a program that counts the ways to hand out the candies.

Two ways are different when some friend receives a different number of candies. For example, giving 1 candy to friend 1 and 2 candies to friend 2 differs from giving 2 candies to friend 1 and 1 candy to friend 2.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100000$ ).

Each of the next $T$ lines contains $n$ and $f$ , separated by a space. ( $1 \le f \le n \le 10000$ )

Output

For each test case, print the number of ways to hand out the candies modulo $1000000007$ , one per line.

Hint

For $n = 6$ and $f = 2$ , the possible ways are $[1, 5]$ and $[5, 1]$ .

For $n = 7$ and $f = 2$ , the possible ways are $[1, 6]$ , $[2, 5]$ , $[3, 4]$ , $[4, 3]$ , $[5, 2]$ , $[6, 1]$ .

Examples2

Example 1
Input
```
5
6 2
7 2
6 3
6 4
7 4
```
Expected output
```
2
6
9
10
20
```
Example 2
Input
```
1
1 1
```
Expected output
```
1
```