{"raw_statement":[{"iden":"statement","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 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:\n\nint fast_max(int n, int a\\[\\]) { \n    int ans = 0;\n    int offset = 0;\n    for (int i = 0; i < n; ++i)\n        if (ans < a\\[i\\]) {\n            ans = a\\[i\\];\n            offset = 0;\n        } else {\n            offset = offset + 1;\n            if (offset == k)\n                return ans;\n        }\n    return ans;\n}\n\nThat 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.\n\nNow 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."},{"iden":"input","content":"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_."},{"iden":"output","content":"Output the answer to the problem modulo 109 + 7."},{"iden":"examples","content":"Input\n\n5 2\n\nOutput\n\n22\n\nInput\n\n5 3\n\nOutput\n\n6\n\nInput\n\n6 3\n\nOutput\n\n84"},{"iden":"note","content":"Permutations from second example:\n\n\\[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\\]."}],"translated_statement":[{"iden":"statement","content":"一天，Petya 在解决一个非常有趣的问题。尽管他使用了许多优化技巧，他的程序仍然获得了“超时”（Time limit exceeded）的 verdict。Petya 对他的程序进行了彻底分析，发现他用于在包含 #cf_span[n] 个正整数的数组中寻找最大值的函数过于缓慢。绝望之下，Petya 决定使用一个出人意料的优化，引入参数 #cf_span[k]，于是他的函数现在包含以下代码：\n\n该函数迭代检查数组元素，记录中间最大值，如果在连续 #cf_span[k] 次迭代后该最大值仍未改变，则将其作为答案返回。\n\n现在 Petya 想要知道他函数的错误率。他请你找出：在所有从 #cf_span[1] 到 #cf_span[n] 的整数的排列中，有多少个排列使得该函数的返回值不等于 #cf_span[n]。由于这个数可能非常大，请输出答案对 #cf_span[109 + 7] 取模的结果。\n\n输入仅一行，包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 106]），用空格分隔，分别表示排列的长度和参数 #cf_span[k]。\n\n请输出该问题的答案，对 #cf_span[109 + 7] 取模。\n\n第二个样例中的排列：\n\n#cf_span[[4, 1, 2, 3, 5]], #cf_span[[4, 1, 3, 2, 5]], #cf_span[[4, 2, 1, 3, 5]], #cf_span[[4, 2, 3, 1, 5]], #cf_span[[4, 3, 1, 2, 5]], #cf_span[[4, 3, 2, 1, 5]]。\n\n"},{"iden":"input","content":"输入仅一行，包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 106]），用空格分隔，分别表示排列的长度和参数 #cf_span[k]。"},{"iden":"output","content":"请输出该问题的答案，对 #cf_span[109 + 7] 取模。"},{"iden":"examples","content":"输入\n5 2\n输出\n22\n\n输入\n5 3\n输出\n6\n\n输入\n6 3\n输出\n84"},{"iden":"note","content":"第二个样例中的排列：#cf_span[[4, 1, 2, 3, 5]], #cf_span[[4, 1, 3, 2, 5]], #cf_span[[4, 2, 1, 3, 5]], #cf_span[[4, 2, 3, 1, 5]], #cf_span[[4, 3, 1, 2, 5]], #cf_span[[4, 3, 2, 1, 5]]。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n, k \\in \\mathbb{N} $ with $ 1 \\leq n, k \\leq 10^6 $.\n\nLet $ \\pi $ be a permutation of $ \\{1, 2, \\dots, n\\} $.\n\nDefine a function $ f(\\pi, k) $ that iterates through $ \\pi $, maintaining a running maximum $ m $. After every $ k $ consecutive steps without updating $ m $, the function returns $ m $.\n\nThe function fails if $ f(\\pi, k) \\ne n $, i.e., it returns a value less than $ n $ before encountering $ n $, due to $ k $ consecutive non-updates.\n\nWe are to compute the number of permutations $ \\pi \\in S_n $ such that $ f(\\pi, k) \\ne n $, modulo $ 10^9 + 7 $.\n\n---\n\n**Formal Statement:**\n\nLet $ M = n $. The function fails if the maximum element $ n $ appears **after** a run of $ k $ consecutive elements, all less than the current maximum at the start of the run, and the current maximum never becomes $ n $ before that.\n\nEquivalently: the function returns the maximum value seen in the prefix of $ \\pi $ up to the first point where $ k $ consecutive elements do not update the running maximum. This value is less than $ n $ if and only if $ n $ appears **after** some position $ i $ such that the last $ k $ elements before $ n $ (i.e., positions $ i-k+1 $ to $ i $) were all less than the maximum among the first $ i $ elements, and that maximum is $ < n $.\n\nBut since $ n $ is the global maximum, the function fails **if and only if** the element $ n $ appears **after** the first occurrence of a block of $ k $ consecutive elements that do not increase the running maximum — and this block occurs before $ n $ is seen.\n\nThis happens **if and only if** the maximum among the first $ m $ elements (for some $ m $) is some value $ < n $, and the next $ k $ elements are all less than or equal to that maximum — i.e., the maximum does not update for $ k $ steps — and $ n $ has not yet appeared.\n\nTherefore, the function returns a value $ < n $ if and only if $ n $ is **not** among the first $ k $ elements **and** there exists a prefix ending at position $ i \\leq n - k $ such that the maximum in $ \\pi[1..i] $ is $ m < n $, and $ \\pi[i+1], \\pi[i+2], \\dots, \\pi[i+k] $ are all $ \\leq m $, and $ n \\notin \\{ \\pi[1], \\dots, \\pi[i+k] \\} $.\n\nBut a simpler characterization:\n\n> The function fails if and only if the element $ n $ appears **after** the first $ k $ elements **and** the maximum among the first $ k $ elements is never surpassed in the next $ k $ elements — i.e., the global maximum $ n $ is not seen within the first $ k $ positions, and then the next $ k $ elements are all less than or equal to the maximum of the first $ k $.\n\nWait — actually, the function checks after **every** $ k $ steps. So if the maximum doesn’t update for $ k $ consecutive steps, it returns immediately.\n\nSo the function will return early if, at any point $ i \\geq k $, the maximum has not changed in the last $ k $ steps (i.e., positions $ i-k+1 $ to $ i $), and $ n $ has not been seen yet.\n\nThus, the function returns early **if and only if** there exists an index $ i \\in [k, n-1] $ such that:\n\n- $ \\pi[i] $ is the maximum among $ \\pi[1..i] $,\n- $ \\pi[i - k + 1], \\pi[i - k + 2], \\dots, \\pi[i] $ are all $ \\leq \\pi[i] $,\n- and $ \\pi[i] < n $,\n- and $ n \\notin \\{ \\pi[1], \\dots, \\pi[i] \\} $.\n\nBut since $ \\pi[i] $ is the maximum so far, and $ < n $, and the last $ k $ elements are $ \\leq \\pi[i] $, then the function returns $ \\pi[i] $ at step $ i $, and never sees $ n $.\n\nThus, the function fails if $ n $ appears **after** the first position $ i \\geq k $ such that the maximum of the first $ i $ elements remains unchanged for the last $ k $ steps.\n\nThis is equivalent to:\n\n> The element $ n $ appears at position $ j > k $, and the maximum among the first $ j-1 $ elements is $ m < n $, and this maximum $ m $ appears at some position $ i \\leq j - k $, and all elements from position $ i $ to $ j-1 $ are $ \\leq m $.\n\nBut since $ m $ is the maximum of the first $ j-1 $ elements, and $ n $ is at position $ j $, the condition for early return is that **the maximum $ m $ of the first $ j-1 $ elements appears at or before position $ j - k $**, and all elements from $ j - k + 1 $ to $ j - 1 $ are $ \\leq m $.\n\nSo, for the function to fail, $ n $ must be at some position $ j \\in [k+1, n] $, and the maximum among the first $ j-1 $ elements must appear at or before position $ j - k $, and all elements from position $ j - k + 1 $ to $ j - 1 $ must be $ \\leq $ that maximum.\n\nBut note: if the maximum among the first $ j-1 $ elements appears at position $ i \\leq j - k $, then from $ i $ to $ j-1 $, no larger element appears, so the last $ k $ elements before $ j $ (positions $ j-k $ to $ j-1 $) are all $ \\leq $ that maximum, so the function would have returned at position $ j-1 $ if $ j - 1 \\geq k $, i.e., $ j \\geq k+1 $.\n\nThus, **the function fails if and only if $ n $ is not among the first $ k $ elements, and the maximum among the first $ j-1 $ elements (where $ j $ is the position of $ n $) appears at or before position $ j - k $**.\n\nBut since $ j $ is the position of $ n $, and $ j > k $, then the maximum among the first $ j-1 $ elements is some $ m < n $, and for the function to return early, we require that $ m $ appears at or before position $ j - k $, so that the $ k $ elements from $ j-k $ to $ j-1 $ are all $ \\leq m $.\n\nThus, the condition is:\n\n> Let $ j $ be the position of $ n $. Then $ j > k $, and the maximum of $ \\pi[1..j-1] $ appears at some position $ i \\leq j - k $.\n\nBut note: if the maximum of $ \\pi[1..j-1] $ appears at position $ i \\leq j - k $, then since $ i \\leq j - k $, the interval $ [i, j-1] $ has length $ \\geq k $, and since no element larger than $ m $ appears in $ [i, j-1] $, then in particular, the last $ k $ elements before $ j $ (positions $ j-k $ to $ j-1 $) are all $ \\leq m $, so the function returns $ m $ at step $ j-1 $.\n\nThus, the number of bad permutations is:\n\n$$\n\\sum_{j = k+1}^{n} \\left[ \\text{number of permutations where } n \\text{ is at position } j, \\text{ and the maximum of } \\pi[1..j-1] \\text{ appears at or before position } j - k \\right]\n$$\n\nLet’s fix $ j $, the position of $ n $.\n\nThen the first $ j-1 $ positions contain $ j-1 $ distinct numbers from $ \\{1, 2, \\dots, n-1\\} $.\n\nLet $ m $ be the maximum among these $ j-1 $ elements. For the function to fail, $ m $ must appear in the first $ j - k $ positions.\n\nSo: among the $ j-1 $ elements before $ n $, the maximum must lie in the first $ j - k $ positions.\n\nThe number of ways to choose the set of $ j-1 $ elements from $ \\{1, \\dots, n-1\\} $: $ \\binom{n-1}{j-1} $.\n\nGiven that set, the maximum among them is fixed: it’s the largest number in the chosen set.\n\nWe need this maximum to appear in the first $ j - k $ positions of the $ j-1 $ positions.\n\nThe number of ways to arrange the $ j-1 $ elements such that the maximum appears in the first $ j - k $ positions:\n\n- The maximum must be placed in one of the first $ j - k $ positions: $ j - k $ choices.\n- The remaining $ j - 2 $ elements can be arranged arbitrarily in the remaining $ j - 2 $ positions: $ (j - 2)! $ ways.\n\nSo for fixed $ j $, the number of such permutations is:\n\n$$\n\\binom{n-1}{j-1} \\cdot (j - k) \\cdot (j - 2)!\n$$\n\nThen multiply by $ (n - j)! $ for the arrangement of elements after $ n $.\n\nWait — no: the entire permutation is determined by:\n\n- Choosing which $ j-1 $ elements are before $ n $: $ \\binom{n-1}{j-1} $\n- Arranging those $ j-1 $ elements such that the maximum is in the first $ j - k $ positions: as above, $ (j - k) \\cdot (j - 2)! $\n- The remaining $ n - j $ elements (after $ n $) can be arranged arbitrarily: $ (n - j)! $\n\nSo total for fixed $ j $:\n\n$$\n\\binom{n-1}{j-1} \\cdot (j - k) \\cdot (j - 2)! \\cdot (n - j)!\n$$\n\nSimplify:\n\n$$\n\\binom{n-1}{j-1} = \\frac{(n-1)!}{(j-1)!(n-j)!}\n$$\n\nSo:\n\n$$\n\\frac{(n-1)!}{(j-1)!(n-j)!} \\cdot (j - k) \\cdot (j - 2)! \\cdot (n - j)! = (n-1)! \\cdot \\frac{(j - k) \\cdot (j - 2)!}{(j-1)!}\n$$\n\nNote: $ \\frac{(j - 2)!}{(j-1)!} = \\frac{1}{j-1} $\n\nSo:\n\n$$\n(n-1)! \\cdot \\frac{j - k}{j - 1}\n$$\n\nThus, for each $ j \\in [k+1, n] $, the number of bad permutations with $ n $ at position $ j $ is:\n\n$$\n(n-1)! \\cdot \\frac{j - k}{j - 1}\n$$\n\nTherefore, total number of bad permutations is:\n\n$$\n(n-1)! \\sum_{j = k+1}^{n} \\frac{j - k}{j - 1}\n$$\n\nLet $ i = j - 1 $, then $ j = i + 1 $, and when $ j = k+1 $, $ i = k $; when $ j = n $, $ i = n - 1 $\n\nSo:\n\n$$\n(n-1)! \\sum_{i = k}^{n-1} \\frac{(i + 1) - k}{i} = (n-1)! \\sum_{i = k}^{n-1} \\left(1 + \\frac{1 - k}{i}\\right) = (n-1)! \\sum_{i = k}^{n-1} \\left(1 + \\frac{1 - k}{i}\\right)\n$$\n\nWait, better:\n\n$$\n\\frac{j - k}{j - 1} = \\frac{(j - 1) - (k - 1)}{j - 1} = 1 - \\frac{k - 1}{j - 1}\n$$\n\nSo:\n\n$$\n\\sum_{j = k+1}^{n} \\frac{j - k}{j - 1} = \\sum_{j = k+1}^{n} \\left(1 - \\frac{k - 1}{j - 1}\\right) = (n - k) - (k - 1) \\sum_{i = k}^{n-1} \\frac{1}{i}\n$$\n\nWhere $ i = j - 1 $\n\nSo total bad permutations:\n\n$$\n(n-1)! \\left[ (n - k) - (k - 1) \\sum_{i = k}^{n-1} \\frac{1}{i} \\right]\n$$\n\nBut this is not integer! We must have made a mistake.\n\nWait — no, we must have made a mistake in the derivation.\n\nLet’s go back.\n\nWe had:\n\nFor fixed $ j $, number of bad permutations with $ n $ at position $ j $:\n\n$$\n\\binom{n-1}{j-1} \\cdot (j - k) \\cdot (j - 2)! \\cdot (n - j)!\n$$\n\nBut $ \\binom{n-1}{j-1} \\cdot (j - 2)! \\cdot (n - j)! = \\frac{(n-1)!}{(j-1)!} \\cdot (j - 2)! \\cdot (n - j)! = (n-1)! \\cdot \\frac{(j - 2)!}{(j-1)!} \\cdot (n - j)! $\n\nWait, we forgot: the $ (n - j)! $ cancels with the denominator from the binomial, but we have:\n\n$$\n\\binom{n-1}{j-1} \\cdot (n - j)! = \\frac{(n-1)!}{(j-1)! (n - j)!} \\cdot (n - j)! = \\frac{(n-1)!}{(j-1)!}\n$$\n\nThen multiplied by $ (j - k) \\cdot (j - 2)! $\n\nSo total:\n\n$$\n\\frac{(n-1)!}{(j-1)!} \\cdot (j - k) \\cdot (j - 2)! = (n-1)! \\cdot (j - k) \\cdot \\frac{(j - 2)!}{(j-1)!} = (n-1)! \\cdot (j - k) \\cdot \\frac{1}{j - 1}\n$$\n\nYes, so:\n\n$$\n\\text{Bad for fixed } j: \\quad (n-1)! \\cdot \\frac{j - k}{j - 1}\n$$\n\nSum over $ j = k+1 $ to $ n $:\n\n$$\n\\text{Total bad} = (n-1)! \\sum_{j=k+1}^{n} \\frac{j - k}{j - 1}\n$$\n\nLet $ r = j - 1 $, then $ r = k $ to $ n-1 $, $ j - k = r + 1 - k $\n\nSo:\n\n$$\n\\sum_{r=k}^{n-1} \\frac{r + 1 - k}{r} = \\sum_{r=k}^{n-1} \\left(1 + \\frac{1 - k}{r}\\right) = (n - k) + (1 - k) \\sum_{r=k}^{n-1} \\frac{1}{r}\n$$\n\nSo:\n\n$$\n\\text{Total bad} = (n-1)! \\left[ (n - k) + (1 - k) \\sum_{r=k}^{n-1} \\frac{1}{r} \\right]\n$$\n\nBut this is not an integer? But number of permutations must be integer.\n\nWait, no — $ \\sum_{r=k}^{n-1} \\frac{1}{r} $ is a rational number, and multiplied by $ (n-1)! $, it becomes integer.\n\nIndeed, $ (n-1)! \\cdot \\frac{1}{r} $ is integer for $ r \\leq n-1 $, since $ r $ divides $ (n-1)! $.\n\nSo we can write:\n\n$$\n\\text{Answer} = (n-1)! \\sum_{r=k}^{n-1} \\frac{r + 1 - k}{r} = (n-1)! \\sum_{r=k}^{n-1} \\left(1 + \\frac{1 - k}{r}\\right)\n$$\n\nBut better to leave as:\n\n$$\n\\boxed{\n\\text{Answer} = (n-1)! \\sum_{j=k+1}^{n} \\frac{j - k}{j - 1}\n}\n$$\n\nOr equivalently:\n\n$$\n\\boxed{\n\\text{Answer} = (n-1)! \\sum_{i=k}^{n-1} \\frac{i + 1 - k}{i}\n}\n$$\n\nWe can also write:\n\n$$\n\\sum_{i=k}^{n-1} \\frac{i + 1 - k}{i} = \\sum_{i=k}^{n-1} \\left(1 + \\frac{1 - k}{i}\\right) = (n - k) + (1 - k) H_{n-1,k}\n$$\n\nwhere $ H_{n-1,k} = \\sum_{i=k}^{n-1} \\frac{1}{i} $ is the partial harmonic sum.\n\nBut for computation, we can precompute harmonic sums modulo $ 10^9 + 7 $ using modular inverses.\n\nNote: We are working modulo $ M = 10^9 + 7 $.\n\nSo algorithm:\n\n- Precompute factorials up to $ \\max(n) = 10^6 $.\n- Precompute harmonic sums $ H[i] = \\sum_{j=1}^i \\frac{1}{j} \\mod M $, using modular inverses.\n- Then $ \\sum_{i=k}^{n-1} \\frac{1}{i} = H[n-1] - H[k-1] $\n- Then compute:\n  $$\n  \\text{ans} = (n-1)! \\cdot \\left( (n - k) + (1 - k) \\cdot (H[n-1] - H[k-1]) \\right) \\mod M\n  $$\n\nBut wait: the expression is:\n\n$$\n\\sum_{i=k}^{n-1} \\frac{i + 1 - k}{i} = \\sum_{i=k}^{n-1} \\left(1 + \\frac{1 - k}{i}\\right) = (n - k) + (1 - k) \\sum_{i=k}^{n-1} \\frac{1}{i}\n$$\n\nYes.\n\nSo final formula:\n\n$$\n\\boxed{\n\\text{Answer} = (n-1)! \\cdot \\left( (n - k) + (1 - k) \\cdot \\left( H_{n-1} - H_{k-1} \\right) \\right) \\mod (10^9 + 7)\n}\n$$\n\nWhere $ H_m = \\sum_{i=1}^m \\frac{1}{i} \\mod (10^9 + 7) $, and $ H_0 = 0 $.\n\nBut note: if $ k = 1 $, then the function returns after 1 step — i.e., after first element. So if the first element is not $ n $, it returns early. So bad permutations: all where $ n $ is not first: $ (n-1) \\cdot (n-1)! $\n\nCheck with formula:\n\n$ k = 1 $: then sum from $ j = 2 $ to $ n $ of $ \\frac{j - 1}{j - 1} = \\sum_{j=2}^n 1 = n - 1 $\n\nThen answer = $ (n-1)! \\cdot (n - 1) $, which is $ (n-1) \\cdot (n-1)! = n! - (n-1)! $, but total permutations is $ n! $, and good permutations are those with $ n $ first: $ (n-1)! $, so bad = $ n! - (n-1)! = (n-1) \\cdot (n-1)! $, yes.\n\nSo formula holds.\n\nAnother check: $ k \\geq n $. Then $ j \\geq k+1 > n $, so no such $ j $, sum is 0 → answer = 0. Correct: if $ k \\geq n $, then the function never returns early (since it needs k consecutive steps, but there are only n elements, and if k >= n, then it will reach the end before returning early). So it always returns n. So bad = 0. Correct.\n\nSo final answer:\n\nLet $ M = 10^9 + 7 $\n\nPrecompute:\n\n- $ fact[i] $ for $ i = 0 $ to $ 10^6 $\n- $ inv[i] $ for $ i = 1 $ to $ 10^6 $ (modular inverses)\n- $ H[i] = H[i-1] + inv[i] \\mod M $\n\nThen:\n\nIf $ k \\geq n $: answer = 0\n\nElse:\n\n$$\n\\text{ans} = fact[n-1] \\cdot \\left( (n - k) + (1 - k) \\cdot (H[n-1] - H[k-1]) \\right) \\mod M\n$$\n\nNote: $ H[k-1] $ is sum from 1 to k-1. So $ H[n-1] - H[k-1] = \\sum_{i=k}^{n-1} \\frac{1}{i} $\n\nYes.\n\nSo output:\n\n$$\n\\boxed{(n-1)! \\cdot \\left( (n - k) + (1 - k) \\cdot \\sum_{i=k}^{n-1} \\frac{1}{i} \\right) \\mod (10^9 + 7)}\n$$","simple_statement":null,"has_page_source":false}