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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-15;
const int N = 1000010;
const int mod = 1e9 + 7;
int n, k, ans;
int fac[N], ifac[N];
double lg[N];
set<int> st[N];
struct P {
int x, y; double w;
P(int X = 0, int Y = 0) : x(X), y(Y) { w = lg[x] - lg[y] - lg[x - y]; }
inline bool operator<(const P &yy)const { return w + eps < yy.w; }
}; priority_queue<P> q;
inline int add(const int &x, const int &y) {
return x + y < mod ? x + y : x + y - mod;
}
inline int mul(const int &x, const int &y) { return (int)((ll)x * y % mod); }
int C(int x, int y) {
if(x < y || x < 0 || y < 0) return 0;
return mul(fac[x], mul(ifac[y], ifac[x - y]));
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) lg[i] = log(i) + lg[i - 1];
fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
for(int i = 2; i <= n; i++) fac[i] = mul(fac[i - 1], i);
for(int i = 2; i <= n; i++) ifac[i] = mul(mod - mod / i, ifac[mod % i]);
for(int i = 2; i <= n; i++) ifac[i] = mul(ifac[i - 1], ifac[i]);
for(int i = 1; i <= n; i++) st[i].insert(i / 2), q.push(P(i, i / 2));
for(; k; --k) {
P u = q.top(); q.pop(), ans = add(ans, C(u.x, u.y));
if(u.y > 0 && !st[u.x].count(u.y - 1))
st[u.x].insert(u.y - 1), q.push(P(u.x, u.y - 1));
if(u.y < u.x && !st[u.x].count(u.y + 1))
st[u.x].insert(u.y + 1), q.push(P(u.x, u.y + 1));
}
printf("%d\n", ans);
return 0;
}
|