Okayu and Korone are playing Phasmophobia.

There are N rooms, numbered 1 to N. Each player has to enter the N rooms in an order.

Let P be the permutation of size N representing the order of rooms Okayu enters, and Q for Korone.

Korone doesn't want to be too far from Okayu, so they set up a plan as the following:

• Okayu will enter the rooms in numerical order. Formally, P = {1, 2, 3, ... N}.
• Korone will enter the rooms in a way such that |P_i - Q_i| ≤ K for every 1 ≤ i ≤ N.

How many configurations can Korone enter the rooms? Since the answer can be large, print the answer modulo 10⁹ + 7.

Input

The first and only line contains two integers N and K.

Output

Print an integer denoting the number of permutations Q satisfying the conditions above in modulo 10⁹ + 7.

Samples

Input 1:
3 1

Output 1:
3

Input 2:
3 2

Output 2:
6

Explanation

In sample 1, the possible configurations are {1, 2, 3}, {2, 1, 3}, and {1, 3, 2}.

In sample 2, all permutations are valid.

Constraints

1 ≤ N ≤ 1000

1 ≤ K ≤ 5

---

hide comments

	Scape: 2021-03-27 23:20:30 Here is another interesting variation of this problem - https://onlinejudge.org/external/120/12000.pdf
	mareknitka2: 2020-12-27 05:10:18 i never expected okakoro to be first think that i will find at english spoj.