D
e
s
c
r
i
p
t
i
o
n
C
l
a
r
i
s
想要铸一把剑，这把剑必须符合他的审美，具体来说，我们可以把这把剑的不同地方的宽度看成一个序列，这个序列要满足以下条件：
1.
每个元素都是正整数（你的宽度不可能是负数吧）
2.
每个元素不能超过
M
，太宽了如果比
C
l
a
r
i
s
身高还高怎么办（你可以认为
C
l
a
r
i
s
的身高就是
M
）
3.
相邻两个元素的差的绝对值必须是
1
（如果是
0
，则这个地方不是锯齿，杀伤力不够，如果太大，又太丑了）
4.
第一个元素的值必须是
1
（剑尖必须是最窄的地方）
他想知道有多少把长度不超过
N
（即宽度的序列长度不超过
N
）的合法的本质不同的剑。
我们认为两把剑本质不同，当且仅当存在至少一个宽度，在两把剑的宽度序列里面出现次数不一样。
比如
{
1
,
2
,
3
}
和
{
1
,
3
,
2
}
是本质相同的
{
1
,
2
,
3
}
和
{
1
,
2
,
1
}
则是本质不同的
I
n
p
u
t
只有两个整数，表示
N
,
M
(数据保证
N
,
M
≤
2000000
)
O
u
t
p
u
t
只有一个整数，表示答案对
10
9
+
7
取模的结果
S
a
m
p
l
e
I
n
p
u
t
5
3
S
a
m
p
l
e
O
u
t
p
u
t
9
H
I
N
T
样例解释
所有本质不同的合法的剑有如下：
{
1
}
{
1
,
2
}
{
1
,
2
,
3
}
{
1
,
2
,
1
}
{
1
,
2
,
3
,
2
}
{
1
,
2
,
1
,
2
}
{
1
,
2
,
3
,
2
,
3
}
{
1
,
2
,
3
,
2
,
1
}
{
1
,
2
,
1
,
2
,
1
}
S
o
u
r
c
e
B
y
l
y
z
y
S
o
l
u
t
i
o
n
这是一道数论题。首先要研究一下题目“本质不同”所包含的信息。
因为本质不同要求的数字个数不同，所以肯定会想到把数字按照某种顺序排列。
注意到一个性质（举个例子），
{
1
,
2
,
3
,
4
,
5
,
4
,
3
,
2
}
是可以变形为
{
1
,
2
,
3
,
2
,
3
,
4
,
5
,
4
}
于是……就按照
1
、
2
、
3
、
4
、
5…
的顺序排着，然后再向其中的一些位置放入
i
,
i
+
1
，比如在
2
,
3
后面接个
2
,
3
（多出来一个？那就扔最后面）
（不能扔最后？那就肯定是不合法的，简单推一下就知道了）
这就变成了向一个序列中插入一坨数对的问题了，再简化一步，向一堆位置放小球。
m
个相同的球放入
n
个相同的盒子的方案数是
C
n
−
1
m
+
n
−
1
（允许空盒）
问题来了，我们的序列还是不确定的，因为只是要求宽度不超过一个数，长度不超过一个数。
于是乎……枚举……
枚举最大宽度（我们的原始序列是自然数列），因为允许空盒，所以就可以求出“长度不超过“的所有情况
我们向原始序列中一次插入一个数对，所以需要
2
个数字，把最后多一个数的情况同最后没有多的数的情况也计算一次即可。
允许长度为
n
，当前最大元素为
i
，即原始序列长度为
i
，那么就有
C
i
n
−
i
2
和
C
i
n
−
i
−
1
2
，分别是后面没有多余数和后面有一个多余的数的情况。
#include<stdio.h>
#define mod 1000000007
#define F(x,y) (ll)f[x+y-1]*inv[x]%mod*inv[y-1]%mod
#define N 2000005
typedef long long ll;
int n,m,ans=1,f[N],inv[N];
int main()
{
scanf("%d%d",&n,&m);
f[0]=f[1]=inv[0]=inv[1]=1;
for (int i=2;i<=n;i++)
{
f[i]=(ll)f[i-1]*i % mod;
inv[i]=(ll)(mod-mod/i)*inv[mod%i] % mod;
}
for (int i=2;i<=n;i++) inv[i]=(ll)inv[i-1]*inv[i] % mod;
for (int i=2,lim=n<m?n:m;i<=lim;i++)
{
ans=(ans+F((n-i)/2,i)) % mod;
if (i+1<=n) ans=(ans+F((n-i-1)/2,i)) % mod;
}
printf("%d",ans);
}