间隔停靠排班

普及-⏱ 1000ms💾 256MB#P3269🏷️ 动态规划计数

题目描述

一排共 $N$ 个车位需要安排停靠类型:每车位停"重型车"或"轻型车"之一。 为保护路面,要求任意两个停重型车的车位之间至少间隔 $K$ 个停轻型车的车位(即重型车位不能相距太近)。 求满足条件的排法总数,对 $5000011$ 取模。同型车视为不区分。

输入格式

一行两个整数 $N$ 和 $K$($1 \le K \le N \le 2 \times 10^6$)。

输出格式

一行一个整数:排法总数对 $5000011$ 取模的结果。

数据范围

None

样例输入 #1
4 2
样例输出 #1
6
样例输入 #2
1 1
样例输出 #2
2