Problem 2052. -- hee的01串

2052: hee的01串

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 34  Accepted: 5
[Submit][Status][Web Board]

Description

heeWUSTACM大名鼎鼎的扛把子,一天在他玩组合数学的时候正在研究一个01串。但是很不巧,因为某些极为和谐的原因,hee弄丢了他的01串。对于hee来讲最不能忍受的就是放过了某些可以解决的问题,幸运的是他知道这个01串的长度n,而且他还知道这个01串中至少有连续m个数字全为1,所以他决定干脆针对所有可能的01串带入这个问题来解决。但是hee发现这样的01串可能有很多,所以他决定先去吃点东西变大再来解决这个问题。

恰好这个时候hee发现了你,于是他委托你帮他计算这样的01串有多少个,并且希望你能在他吃完东西之前解决这个问题,这样他就能着手下一步的工作了。

Input

多组测试数据。

每行仅含两个整数nm,含义同题面

Output

仅包含一个整数,输出可能的01串数量,答案对1000000007取余

Sample Input

4 3

Sample Output

3

HINT


1<=n,m<=100000

Author

ghdny2015

[Submit][Status][Web Board]