Maximum Element

题意翻译

## 题目描述 从前有一个叫$Petya$的神仙，嫌自己的序列求max太慢了，于是将序列求max的代码改成了下面这个样子： ```cpp 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++; if(offset==k)return ans; } } return ans; } //大括号换行，无多余空格，by wucstdio ``` 这个函数的原理是，如果碰到一个数后面连续的$k$个数都比它小，那么就把这个数当做序列的最大值。 然而很显然，这份代码是错的。这位$Petya$神仙对它出错的情况很感兴趣。于是他找到了同为神仙的你，让你求有多少长度为$n$的排列，这个函数会返回错误的结果，即返回值不是$n$。由于答案过大，你只需要输出这个数对$10^9+7$取模的结果。 ## 输入输出格式 ### 输入格式 一行两个正整数$n$和$k$，表示排列的长度和上面那份代码里的$k$。 ### 输出格式 一行一个整数，表示答案对$10^9+7$取模后的值。

题目描述

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: `<br></br>int fast_max(int n, int a[]) { <br></br> int ans = 0;<br></br> int offset = 0;<br></br> for (int i = 0; i < n; ++i)<br></br> if (ans < a[i]) {<br></br> ans = a[i];<br></br> offset = 0;<br></br> } else {<br></br> offset = offset + 1;<br></br> if (offset == k)<br></br> return ans;<br></br> }<br></br> return ans;<br></br>}<br></br>`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 $ 10^{9}+7 $ .

输入输出格式

输入格式

The only line contains two integers $ n $ and $ k $ ( $ 1<=n,k<=10^{6} $ ), separated by a space — the length of the permutations and the parameter $ k $ .

输出格式

Output the answer to the problem modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

5 2

输出样例 #1

22

输入样例 #2

5 3

输出样例 #2

6

输入样例 #3

6 3

输出样例 #3

84

说明

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

题意翻译

## 题目描述 从前有一个叫$Petya$的神仙，嫌自己的序列求max太慢了，于是将序列求max的代码改成了下面这个样子： ```cpp 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++; if(offset==k)return ans; } } return ans; } //大括号换行，无多余空格，by wucstdio ``` 这个函数的原理是，如果碰到一个数后面连续的$k$个数都比它小，那么就把这个数当做序列的最大值。 然而很显然，这份代码是错的。这位$Petya$神仙对它出错的情况很感兴趣。于是他找到了同为神仙的你，让你求有多少长度为$n$的排列，这个函数会返回错误的结果，即返回值不是$n$。由于答案过大，你只需要输出这个数对$10^9+7$取模的结果。 ## 输入输出格式 ### 输入格式 一行两个正整数$n$和$k$，表示排列的长度和上面那份代码里的$k$。 ### 输出格式 一行一个整数，表示答案对$10^9+7$取模后的值。