Submission #1083816

---

Source Code Expand

#include <bits/stdc++.h>
#define f(a, n) for (int a=0; a<n; a++)
#define F(a, n) for (int a=1; a<=n; a++)
#define ll long long
using namespace std;
const ll MOD = 1000000007;
unordered_map<ll, ll> gmp;
ll pairit(ll a, ll b){
	return (a<<32) + b;	
}
ll g(ll a, ll b){
	if (a==0) return 0;
	if (a==1) return 1;
	ll tmp=pairit(a,b);
	if (gmp.count(tmp)) return gmp[tmp];	
	if (b==0) gmp[tmp] = (g(a-1, 0) + g(a-1, 1) ) %MOD;
	else gmp[tmp] = (g(a, b-1) + g(a-1, b+1)) % MOD;
	return gmp[tmp];
}
ll powa(ll a, ll b){
	if (b<=0) return 1;
	else if (b%2) return (powa((a*a)%MOD,b/2) * a) % MOD;
	return powa((a*a)%MOD,b/2);
}
ll N, K;
int main(){
	ios::sync_with_stdio(false);
	cin>>N>>K;
	cout<<( (g(K, N-K) - g(K-1, N-K+1) + MOD)* powa(2, N-K-1) ) % MOD << endl; 
	return 0;
}

Submission Info

Judge Result