Gym - 101775A - Chat Group 组合数+快速幂取模+逆元

It is said that a dormitory with 6 persons has 7 chat groups ^_^. But the number can be even larger: since every 3 or more persons could make a chat group, there can be 42 different chat groups.

Given N persons in a dormitory, and every K or more persons could make a chat group, how many different chat groups could there be?

Input

The input starts with one line containing exactly one integer T which is the number of test cases.

Each test case contains one line with two integers N and K indicating the number of persons in a dormitory and the minimum number of persons that could make a chat group.

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 109.
• 3 ≤ K ≤ 105.

Output

For each test case, output one line containing "Case #x: y" where x is the test case number (starting from 1) and y is the number of different chat groups modulo 1000000007.

Example

Input

Copy

1
6 3

Output

Copy

Case #1: 42

 题意：
求ans=C(n,k)+C(n,k+1)+....+C(n,n)；

ans=2^n-C(n,0)+C(n,1)+...+C(n,k-1);

2^n可由快速幂取模求出...

C(n,x)=C(n,x-1)*(n-x-1)/x;

这里/x可以通过逆元转化为*inv(x);

因为x在这里与mod互质，所以可以通过inv=(x,mod-2)求出inv;

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const long long mod=1000000007;
int t;
ll n,k;
ll Fast (ll a,ll b)
{
    ll sum=1;
    while (b)
    {
        if(b&1)
        {
            sum=sum*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return sum;
}
int main()
{
    scanf("%d",&t);
    for (int i=1;i<=t;i++)
    {
        scanf("%lld%lld",&n,&k);
        ll sum=Fast(2,n)-1-n;//2^n-C(n,0)-C(n,1);
        ll x=n;
        for (int j=1;j<k-1;j++)
        {
            x=x*(n-j)%mod;
            x=x*Fast(j+1,mod-2)%mod;
            sum=(sum+mod-x)%mod;
        }
        printf("Case #%d: %lld\n",i,sum);
    }
    return 0;
}