描述

传送门：洛谷-1999

0维空间的元素是点，这个毋庸置疑。

2个0维空间的元素可以围成一个1维空间的元素，线段。

4个1维空间的元素可以围成一个2维空间的元素，正方形。

6个2维空间的元素可以围成一个3维空间的元素，正方体。

8个3维空间的元素可以围成一个4维空间的元素，超正方体。

……

一个正方形中，有4个（顶）点，4条线段（边），1个正方形。

一个正方体中，有8个（顶）点，12条线段（棱），6个正方形（面），1个正方体。

……

我们的问题是：给出a与b，请求出：在a维空间的元素中，包含着多少个b维空间的元素。答案可能很大，只需要输出它除以1000000007的余数。

Input

两个整数a,b，以空格隔开。

Output

一个整数，即答案。

Examples

intput
1
3 1
output
1
12

思路

仔细观察
4 4 1
8 12 6 1
可以看出他们的共同点就是一个是$(x+2)^2$的展开式系数，一个是$(x+2)^3$的展开式系数，这时候我们就大胆的猜测$n$维立方体里包含的比他低维度的立方体个数就是$(x+2)^n$的展开式的系数，a维空间的元素中包含个b维空间的元素的个数就是$(x+2)^a$的展开式中$x^b$的系数。(事实证明是对的)

根据二项式定理，我们就得到了公式 $solve(a,b)=C_a^b\cdot2^{a-b}=\frac{a!}{b!(a-b)!}\cdot2^{a-b}$

由于$C_a^b2$和$2^{a-b}$都太大了，但是由于要取模，我们就可以分别用逆元和快速幂求得值。

数据用$long long$来存，否则会爆精度。

逆元和快速幂详见另一篇博客：数论笔记本

代码

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>  
#include<string.h>  
#include<string>   
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = 2.718281828459;
const int mod =1e9+7; 

ll fac(ll x)		//阶乘 
{
	ll ans=1;
	for(int i=1;i<=x;i++)
		ans=(ans*i)%mod;
	return ans;
}

ll x,y;
ll exgcd(ll a,ll b)		//扩展欧几里德求逆元 
{
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    ll r=exgcd(b,a%b);
    ll c=x;
    x=y;
    y=c-a/b*y;
    return r;
}

ll qpow(ll a,ll b)		//快速幂 
{
    ll ans=1;
    a%=mod;
    while(b>0)
    {
        if(b&1)
            ans=(ans*a)%mod;
        b/=2;
        a=(a*a)%mod;
    }
    return ans;
}

int main()
{
	int a,b;ll ans;
	while(cin>>a>>b)
	{
		if(a<b) ans=0;              //特判
		else
		{
			exgcd((fac(b)*fac(a-b))%mod,mod);
			x= x<=0? x+=mod:x;						//保证x>0 
			ans=(((fac(a)*x)%mod)*qpow(2,a-b))%mod;
		}
			cout<<ans<<endl;
	}
	return 0;
}