Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3725
Painting Storages

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There is a straight highway with N storages alongside it labeled by 1,2,3,...,N. Bob asks you to paint all storages with two colors: red and blue. Each storage will be painted with exactly one color.

Bob has a requirement: there are at least M continuous storages (e.g. "2,3,4" are 3 continuous storages) to be painted with red. How many ways can you paint all storages under Bob's requirement?

Input

There are multiple test cases.

Each test case consists a single line with two integers: N and M (0<N, M<=100,000).

Process to the end of input.

Output

One line for each case. Output the number of ways module 1000000007.

Sample Input

4 3 

Sample Output

3

Author: ZHAO, Kui
Contest: ZOJ Monthly, June 2013
Submit    Status