Description

zty特别喜欢爬楼梯。

他在爬楼梯的时候，每一层台阶可能是左脚踏上去的，也可能是右脚踏上去的。

zty踏上第一级台阶有两种方法，左脚或右脚。

当zty的一只脚刚踏上第i阶台阶时，下一步的可能移动方式有：接着迈出该只脚，或是另一只脚

• 如果zty迈出另一只脚，那么他可以踏到第i+1或i+2或……或i+k阶台阶
• 如果zty仍迈出该只脚，由于重心不稳，只能踏到第i+1阶台阶

求zty到第n阶的方案数，答案对10007取模

Format

Input

第一行两个正整数$n, k$，其含义见题目描述

Output

输出走$n$阶台阶的方法总数对10007取模的结果

Samples

1 1

2

2 1

4

3 1

8

4 1

16

5 2

58

Limitation

本题共有10个测试点，每个测试点10分。

对于40%的测试数据，$1\leq n\leq 10, k=1$

对于另外20%的测试数据，$1\leq n\leq 10^6, k=1$

对于另外40%的测试数据，$1\leq n\leq 10^6, 1\leq k\leq 20$