Codeforces Round #818 (Div. 2) D - Madoka and The Corruption Scheme

D. Madoka and The Corruption Scheme

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Madoka decided to entrust the organization of a major computer game tournament "OSU"!

In this tournament, matches are held according to the "Olympic system". In other words, there are 2n2n participants in the tournament, numbered with integers from 11 to 2n2n. There are nn rounds in total in the tournament. In the ii-th round there are 2n−i2n−i matches between two players (one of whom is right, the other is left), after which the winners go further along the tournament grid, and the losing participants are eliminated from the tournament. Herewith, the relative order in the next round does not change. And the winner of the tournament — is the last remaining participant.

But the smaller the participant's number, the more he will pay Madoka if he wins, so Madoka wants the participant with the lowest number to win. To do this, she can arrange the participants in the first round as she likes, and also determine for each match who will win — the participant on the left or right.

But Madoka knows that tournament sponsors can change the winner in matches no more than kk times. (That is, if the participant on the left won before the change, then the participant on the right will win after the change, and if the participant on the right won, then the participant on the left will win after the change).

So, the first image shows the tournament grid that Madoka made, where the red lines denote who should win the match. And the second one shows the tournament grid, after one change in the outcome of the match by sponsors (a match between 11 and 33 players).

Print the minimum possible number of the winner in the tournament, which Madoka can get regardless of changes in sponsors. But since the answer can be very large, output it modulo 109+7109+7. Note that we need to minimize the answer, and only then take it modulo.

Input

The first and the only line contains two integers nn and kk (1≤n≤105,1≤k≤min(2n−1,109)1≤n≤105,1≤k≤min(2n−1,109)) — the number of rounds in the tournament and the number of outcomes that sponsors can change.

Output

Print exactly one integer — the minimum number of the winner modulo 109+7109+7

Examples

input

Copy

1 1

output

Copy

2

input

Copy

2 1

output

Copy

3

input

Copy

3 2

output

Copy

7

Note

In the first example, there is only one match between players 11 and 22, so the sponsors can always make player 22 wins.

The tournament grid from the second example is shown in the picture in the statement.

#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<numeric>
#include<stack>
#include<queue>
#include<set>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f,maxn=1e5+5,mod=1e9+7;
int fac[maxn]={1},fac_inv[maxn]={1};//计算组合数要用的，这种是只计算最底层的组合数，就是C_n^i，差不多就是O(n)
int n,k;
void exgcd(int a,int b,ll &x,ll &y)
{
	if(!b)
	{
		x=1;
		y=0;
	}
	else
	{
		exgcd(b,a%b,y,x);
		y-=a/b*x;
	}
}
void init()
{
	for(int i=1;i<maxn;i++)
	{
		fac[i]=(ll)fac[i-1]*i%mod;
	}
	ll x,y;
	exgcd(fac[maxn-1],mod,x,y);
	fac_inv[maxn-1]=(x%mod+mod)%mod;//这个用exgcd求
	for(int i=maxn-2;i>=0;i--)
	{
		fac_inv[i]=(ll)fac_inv[i+1]*(i+1)%mod;//这样相当于“线性求逆元”了
		//这个递推公式的话，写两个式子    t! *  inv(t!)   ≡1 (mod b)
		//                           (t+1)!*inv((t+1)!)≡1 (mod b)
		//然后拿上面的式子除以下面的式子即可推出（是同余运算，合理的）
	}
}
int qpow(ll a,int p)
{
	int ans=1;
	for(;p;p>>=1,a=a*a%mod)if(p&1)ans=a*ans%mod;
	return ans;
}
int main()
{
	//首先解题的理论基础是不妨设定二叉树上每条斜向左的边为胜，斜向右的为负，
	//在一颗完整二叉树上，任意 i条斜向左边+j条斜向右边 ，只要满足i+j==n都
	//能在二叉树上找到(指的是从跟到叶的路上的边)，并且一种只能找到一条，那
	//么只能改变k次则无法改变那些路径上失败次数大于k的路，其他的路（失败边
	//<=k的）则sponsor可以任意选一条来改，那么我们把数字大的放到失败边多的
	//中，则最终算一下 ΣC_n^i,i>k 的数字有几个，这些就是接近n的，可以让
	//sponsor取不到的数字，那么剩下的最大就是被取走的了，因此题解就是这样
	//当然里面求解的时候还涉及了一些技巧，所以妙不可言！（ps：我学别人的
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin>>n>>k;
	if(k>=n)
	{
		cout<<qpow(2,n);
		return 0;
	}
	init();
	//接下来就是要组合数了
	ll tmp=0;
	for(int i=k+1;i<=n;i++)//如n=3,k=2
	{
		tmp=(tmp+(ll)fac[n]*fac_inv[i]%mod*fac_inv[n-i]%mod)%mod;
	}
	cout<<(qpow(2,n)-tmp+mod)%mod;
	return 0;
}