#6. 爬楼梯

爬楼梯

Description

zty特别喜欢爬楼梯。

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

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

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

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

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

Format

Input

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

Output

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

Samples

1 1
2
2 1
4
3 1
8
4 1
16
5 2
58

Limitation

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

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

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

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