题目描述

​ HL教育园决定要用摆成一排的N（1<=N<=100000）盆花来美化校园，园丁提供的花只有两种颜色：蓝花和红花，且这两种花可以随意挑选，数量不限。

​ 因为蓝花给人的感觉很惊艳，为了协调，校长决定任意两盆蓝花之间至少要摆K盆红花。为了满足这个条件，作为负责人的小x头很疼。

​ 但是数学老师又提出一个问题：在满足校长要求的基础上，一共有多少种摆法。而这个问题只能你去解决了。

输入格式

两个整数N和K

输出格式

一个整数，表示一共有多少种摆法。因为这个数字很大，只需要对5000011取余数即可。

样例数据

input

4 2

output

6

六种可能性是：r r r r；b r r r; rbrr; rrbr; r r r b; b r r b

​ r表示红花，b表示蓝花

数据规模与约定

40%数据保证 N<=100 K<=20

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$