Secret Project Gym - 101972I (组合数+找规律)

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, zstudents 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 109 + 7.

Input

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

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

Output

For each test case, print a single line containing two integers x and y, in which xis 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 109 + 7.

Example

Input

Output

题意：一个柜子上有x层锁，一层锁需要一把钥匙，每个人至少拿一把钥匙，问：至少去m个人才能把锁打开时，最少的锁的数量x，和每个人拿的最少的钥匙数y。

思路：多写几组数据+找找规律+大胆猜测=AC

比如：

3 2 锁的数量x=C(3,2-1) 最少的钥匙数y=C(3-1,2-1);

2 2 锁的数量x=C(2,2-1) 最少的钥匙数y=C(2-1,2-1);

5 4 锁的数量x=C(5,4-1) 最少的钥匙数y=C(5-1,4-1);

5 3 锁的数量x=C(5,3-1) 最少的钥匙数y=C(5-1,3-1);

因此：结果就是C(n,m-1),C(n-1,m-1);

如果对于组合数不太清楚的朋友，可以点击这里https://blog.csdn.net/Daxian911/article/details/85037267

代码如下:

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n,m;
ll fac[maxn];
ll ni[maxn];
ll ksm(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
void init(int n)
{
    fac[0]=1;
    ni[0]=1;
    for(int i=1;i<=n;i++)
    {
        fac[i]=fac[i-1]*i%mod;
    }
    ni[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=1;i--)
    {
        ni[i]=ni[i+1]*(i+1)%mod;
    }
}
ll C(ll n,ll m)
{
    return fac[n]*ni[m]%mod*ni[n-m]%mod;
}
int main()
{
    int T;
    init(100000);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        printf("%lld %lld\n",C(n,m-1),C(n-1,m-1));
    }
	return 0;
}