Codeforces Round #818 (Div. 2)

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 2^n participants in the tournament, numbered with integers from 1 to 2^n. There are nn rounds in total in the tournament. In the ii-th round there are 2^n−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 k 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 1 and 3 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+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≤10^5,1≤k≤min(2^n−1,10^9)) — 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+71

Examples

input

1 1

output

2

input

2 1

output

3

input

3 2

output

7

Note

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

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

 

 

可能二叉树还有这个性质吧。

就不如说n=3，我如果叶子节点到根节点有两条没通，其实是一个组合数。

类似下面我画的这个图。 

 7：100

6：010

4：001

它是一个排列，你把坐标换成7、6、5就行。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e6+10;
ll f[N],ivf[N];
ll ksm(ll x,ll n)
{
    ll res=1;
    while(n)
    {
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
void init()
{
    f[0]=1;
    for(int i=1; i<=1e6; i++) f[i]=1ll*f[i-1]*i%mod;
    int m=1e6;
    ivf[m]=ksm(f[m],mod-2);
    for(int i=m-1; i>=0; i--)
    {
        ivf[i]=1ll*ivf[i+1]*(i+1)%mod;
    }
}
ll C(ll n,ll m)
{
    return 1ll*f[n]*1ll*ivf[m]%mod*ivf[n-m]%mod;
}
void solve()
{
    int n,k;
    cin>>n>>k;
    if(k>=n)
    {
        cout<<ksm(2,n)%mod;
        return;
    }
    else
    {
        ll ans=0;
        for(int i=0; i<=min(n,k); i++)
        {
            ans=(ans+C(n,i)%mod)%mod;
        }
        cout<<ans;
        return;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
 
    int T;
    T=1;
    while(T--)
    {
        solve();
    }
    return 0;
}