Andrew is planning something and he needs your help. Andrew needs your help to determine how many permutations of the first $N$ positive integers are good.

A permutation $p$ is good if there exists an index $i$ $(1\le i\le N-1)$ such that $|p_{i+1}-p_i|=D$.

Since the answer might be very large, output it modulo ${10}^9+7$.

Constraints

$2\le N\le {10}^6$
$N\le 2D<2N$

Subtask 1 [10%]

$2\le N\le 8$

Subtask 2 [30%]

$2\le N\le 2000$

Subtask 3 [60%]

No additional constraints.

Input Specification

The first and only line contains $N$ $(2\le N\le {10}^6)$ and $D$ $(N\le 2D<2N)$.

Output Specification

Output the number of good permutations, modulo ${10}^9+7$.

Sample Input 1

3 2

Sample Output 1

4

Explanation

The good permutations are $\{1,3,2\}$, $\{2,1,3\}$, $\{2,3,1\}$, and $\{3,1,2\}$.

Sample Input 2

838383 833883

Sample Output 2

711361423