题目描述

一排喷泉有 $n$ 个喷头，初始时全部处于"开启"状态。每次操作可以改变连续 $k$ 个喷头的状态（开启变关闭，关闭变开启）。问：经过若干次操作后，最多能形成多少种不同的喷泉状态？由于答案可能很大，请对 $10^9+7$ 取模。

输入格式

一行，两个正整数 $n$ 和 $k$，用空格隔开。

输出格式

一个整数，表示不同喷泉状态数对 $10^9+7$ 取模后的结果。

样例

3 2

4

数据范围与提示

• 对于 $30\%$ 的数据：$n \le 10$
• 对于 $60\%$ 的数据：$n \le 1000$
• 对于 $100\%$ 的数据：$1 \le k \le n \le 10^5$