题意：将一个整数n分拆成小于或等于它的正整数相加，共有2^(n-1)种拆法，问在所有的拆法中，数字k出现的次数(1 <= n, k <= 1000000000，共有T(1 <= T <= 10000)组测试数据)，结果模1000000007。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4602
——>>三种情况：
1、当k > n时，结果为0；
2、当k == n时，结果为1；
3、当k < n时，把n分成n个1，要取出k个连续的1组成1个k，设取出来的这k个1的第一位是b，则b的左边有b-1个1，根据题意得，将b-1分拆共有2^(b-2)种拆法，[b, b+k-1]是取的连续的1，它的右边还有n - (b+k-1)个1，n - (b+k-1)有2^[n - (b+k-1) - 1] = 2^(n-b-k)种拆法，所以，当取定这个位置的k时，有2^(b-2) * 2^(n-b-k) = 2^(n-k-2)种情况（发现与b无关），这里没有重复，因为计算每个位置的k只计算他自己一次，而不管其他地方是否也出现了k。
当b == 1时——>b的左边没有1，右边——>2^(n-b-k) = 2^(n-1-k)；
当b == n-k+1时——>组成的k的右边没有1，左边——>2^(b-2) = 2^(n-1-k)；
当2 <= b <= n-k时——>就有(n-k-2+1) * 2^(b-2) * 2^(n-b-k)；
总共就是2^(n-b-k) + 2^(n-1-k) + (n-k-2+1) * 2^(b-2) * 2^(n-b-k) = (n-k+3)*2^(n-k-2)。
由于指数大，应用快速幂。
#include <cstdio>using namespace std;const int mod = 1000000000 + 7;int pow_mod(int n)
{if(n == 0) return 1;if(n == 1) return 2;int x = pow_mod(n / 2);long long ans = (long long)x * x % mod;if(n % 2 != 0) ans = ans * 2 % mod;return (int)ans;
}int main()
{int T, n, k, ret;scanf("%d", &T);while(T--){scanf("%d%d", &n, &k);if(k > n) ret = 0;else if(k == n) ret = 1;else if(k == n-1) ret = 2;else ret = (int)((long long)(n - k + 3) * pow_mod(n - k - 2) % mod);printf("%d\n", ret);}return 0;
}