1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
using namespace std;
using LL = long long;
const LL mod =(LL) 1e9+7;
const int maxn = 8100001;
LL f[maxn];
LL n, m;
void () {
f[0] = f[1] = 1;
for(int i = 2; i < maxn; i++) f[i] = (f[i-1] * i) % mod;
}
LL mul(LL x, LL n) {
LL ret = 1;
while(n) {
if(n & 1) ret = (ret * x) % mod;
n >>= 1;
x = (x * x) % mod;
}
return ret;
}
LL exgcd(LL a, LL b, LL &x, LL &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
else {
LL ret = exgcd(b, a%b, x, y);
LL tmp = x;
x = y;
y = tmp - a / b * y;
return ret;
}
}
LL inv(LL a) {
LL x, y;
exgcd(a, mod, x, y);
return (x % mod + mod) % mod;
}
LL C(LL x, LL y) {
return f[x] * inv(f[x-y]) % mod * inv(f[y]) % mod;
}
LL gao() {
LL ret = 0;
for(LL k = 0; k <= m; k++) {
if(k % 2 == 0) {
ret += (f[2*n-i]*C(m,i)%mod)*mul(2LL,i)%mod;
ret %= mod;
}
else {
ret -= (f[2*n-i]*C(m,i)%mod)*mul(2LL,i)%mod;
ret += mod;
ret %= mod;
}
}
if(ret < 0) ret += mod;
return ret % mod;
}
signed main() {
init();
int T, _ = 1;
scanf("%d", &T);
while(T--) {
cin >> n >> m;
cerr << "Case #" << _ << " Done." << endl;
printf("Case #%d: %lldn", _++, gao());
}
return 0;
}
|
近期评论