题意
给你一个数n，把它写成几个正整数相加的形式，即把n拆开成若干段，把所有可能的式子里正整数 k 出现的次数取模是多少。
分析
特判 k>=n 的情况。
k<n时：问题相当于n个点排一行，选其中连续的k个点，其他点的间隔情况有多少种。
n个点原来有n-1个两两之间的间隔，当n-k>1时，如果k个点不包含端点，那么剩下的间隔就是：n-1 -（k+1）=n-k-2。此时每个间隔，就有隔或者不隔2种情况，选这k个点的方法又有n-k-1种，所以共有2的n-k-2次方 * （n-k-1）种间隔方案。
如果包含端点，剩下的间隔就是：n-1 -k。因为两个端点，所以有2*（2的n-1-k次方）种间隔方案。
所以总共有2n-k-2*（n-1-k）+2*2n-1-k=（n-3-k）*2n-k-2种方案。
注意到如果n-k=1，那么只有包含端点的情况，答案就是2，故也进行特判。
然后用快速幂取模就可以啦。
代码
#include<cstdio>
#define ll long long
ll m=1e9+;
ll qpow(int b)
{
ll a=,ans=;
while(b)
{
if(b&)ans=ans*a%m;
a=a*a%m;
b>>=;
}
return ans;
}
int main()
{
ll t,n,k;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&k);
if(n<k)
printf("0\n");
else if(n==k)
printf("1\n");
else if(n-k==)
printf("2\n");
else
printf("%lld\n",(n-k+)*qpow(n-k-)%m);
}
return ;
}