CPDUEL5C - Phasmophobia

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 |Pi - Qi| ≤ K for every 1 ≤ i ≤ N.

How many configurations can Korone enter the rooms? Since the answer can be large, print the answer modulo 109 + 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 109 + 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


Added by:Maximilliano
Date:2020-11-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem

hide comments
2021-03-27 23:20:30 Scape
Here is another interesting variation of this problem - https://onlinejudge.org/external/120/12000.pdf
2020-12-27 05:10:18
i never expected okakoro to be first think that i will find at english spoj.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.