Permutaion 输出的计算问题

Question

Problem Description
As we known, there are N! permutations of {1,2,...N}. Now you are requested to find how many permutations satisfying that, the difference of every two adjacent numbers is not more than K. Because the answer may be quite large, you only need to output the answer module (%) 1,000,000,007.

You can assume 2 <= N <= 50 and 0 <= K <= 4.

Input
There are several lines of the input. Each line indicates one test case, and contains two numbers N and K.

Output
Output one line for each test case, indicating the answer module 1,000,000,007.

Sample Input
4 2

Sample Output
12

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# Permutation
permutations <- function(n){
  if (n == 1) return(1)
  return(factorial(n)*sum(permutations(n-1)))
}

# Solution
solution <- function(N,K){
  # The result should be returned modulo 1,000,000,007.
  mod_result <- 0
  # If n is even, then n/2 will have a permutation with length n/2 + 1,
  # which means it's possible to construct a permutation by adding or removing
  # a number from the end of the permutation of length n/2 + 1.
  if (N % 2 == 0) {
    mod_result <- permutations((N+1)/2)%/%1e6
    mod_result <- mod_result*permutations(N-1)%/%1e6
  } else {
    mod_result <- permutations(N/2)%/%1e6
  }
  mod_result <- mod_result%/%K
  mod_result <- mod_result%/%1e6
  mod_result <- mod_result%/%1e6
  return(mod_result)
}