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