Problem Description

There are $N$ blocks numbered from $1$ to $N$. Additionally, an integer $K$ is given.

Kou, the wizard, is trying to cast a spell to erase these blocks. He can cast the following spell:

• Choose an integer pair $(l, r)$ such that $1 \leq l \leq r \leq N$ and $r - l \geq K$, and erase all blocks (that have not been erased yet) with numbers from $l$ to $r$.

In other words, there are $(N-K) \times (N-K+1) / 2$ types of spells he can cast.

There are $2^{(N-K) \times (N-K+1) / 2}$ combinations of whether to cast each spell or not. Kou is interested in how many of these combinations can eventually erase all blocks.

For Kou, determine how many combinations can eventually erase all blocks. Since the answer can be very large, output the answer modulo $10^9+7$.

Input Format

The input is given from the standard input in the following format:

$N$ $K$

Output Format

Output the number of combinations that can eventually erase all blocks, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3 1

Sample Output #1

5

Sample Input #2

10 5

Sample Output #2

30784

Sample Input #3

5000 250

Sample Output #3

844653816

Notes/Hints

Constraints

• $1 \leq N \leq 5000$
• $0 \leq K \leq N-1$
• All values given are integers.

Sample Explanation 1

Kou can cast spells with $(l, r) = (1,2), (2,3), (1,3)$. There are 5 combinations that can eventually erase all blocks:
- $(1,2)$ and $(2,3)$
- $(1,2)$ and $(1,3)$
- $(1,2)$ and $(2,3)$ and $(1,3)$
- $(2,3)$ and $(1,3)$
- $(1,3)$

见题面 Input 部分

见题面 Output 部分