405483: GYM101972 I Secret Project

There are n students working on a secret project, this project is very important and unique, so they decided to keep it safe, and protect it from leakage.

The students will put all the project's documents in a cabinet that has x locks, and each student will take a set of y unique keys, such that each key can open only one lock. The cabinet can be opened if and only if m or more of the students are present.

Each of the cabinet's lock has an infinite number of keys that can open it, and students may have different or similar sets of keys. In order to open the cabinet, z students must be presented (m ≤ z), such that these students have at least one key for each cabinet's lock.

Your task is to find minimum values of x and y. More formally, your task is to find what is the minimum number of locks needed and what is the minimum number of keys to the locks each student must carry such that the cabinet can be opened if and only if m or more of the students are present. Since these numbers are large, you need to print them modulo 10⁹ + 7.

The first line contains an integer T (1 ≤ T ≤ 10⁵) specifying the number of test cases.

Each test case consists of a single line containing two integers n and m (1 ≤ m ≤ n ≤ 10⁵), in which n is the number of students, and m is the minimum number of students that must be present to open the cabinet.

For each test case, print a single line containing two integers x and y, in which x is the smallest number of locks needed, and y is the smallest number of keys to the locks each student must carry. Both numbers must be printed modulo 10⁹ + 7.

4
3 2
2 2
5 4
5 3

3 2
2 1
10 4
10 6

In the first test case, there are 3 students, and at least 2 of them must present to open the cabinet. The optimal answer is to use 3 locks for the cabinet, such that each student will take 2 keys as follow: the 1^st student takes keys of the 1^st and 2^nd locks, the 2^nd student takes keys of the 1^st and 3^rd locks, and the 3^rd student takes keys of the 2^nd and 3^rd locks. This distribution will ensure that at least two students must present in order to unlock all locks and open the cabinet.