E. Maximum Element

Codeforces

IDCF886E

Time2000ms

Memory256MB

Difficulty—

combinatoricsdpmath

One day Petya was solving a very interesting problem. But although he used many optimization techniques, his solution still got Time limit exceeded verdict. Petya conducted a thorough analysis of his program and found out that his function for finding maximum element in an array of _n_ positive integers was too slow. Desperate, Petya decided to use a somewhat unexpected optimization using parameter _k_, so now his function contains the following code: int fast_max(int n, int a\[\]) { int ans = 0; int offset = 0; for (int i = 0; i < n; ++i) if (ans < a\[i\]) { ans = a\[i\]; offset = 0; } else { offset = offset + 1; if (offset == k) return ans; } return ans; } That way the function iteratively checks array elements, storing the intermediate maximum, and if after _k_ consecutive iterations that maximum has not changed, it is returned as the answer. Now Petya is interested in fault rate of his function. He asked you to find the number of permutations of integers from 1 to _n_ such that the return value of his function on those permutations is not equal to _n_. Since this number could be very big, output the answer modulo 109 + 7. ## Input The only line contains two integers _n_ and _k_ (1 ≤ _n_, _k_ ≤ 106), separated by a space — the length of the permutations and the parameter _k_. ## Output Output the answer to the problem modulo 109 + 7. [samples] ## Note Permutations from second example: \[4, 1, 2, 3, 5\], \[4, 1, 3, 2, 5\], \[4, 2, 1, 3, 5\], \[4, 2, 3, 1, 5\], \[4, 3, 1, 2, 5\], \[4, 3, 2, 1, 5\].

Samples

Input #1

5 2

Output #1

Input #2

5 3

Output #2

Input #3

6 3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "E. Maximum Element",
    "description": {
      "content": "One day Petya was solving a very interesting problem. But although he used many optimization techniques, his solution still got Time limit exceeded verdict. Petya conducted a thorough analysis of his ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF886E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "One day Petya was solving a very interesting problem. But although he used many optimization techniques, his solution still got Time limit exceeded verdict. Petya conducted a thorough analysis of his ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments