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
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. |
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 |