{"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 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.\n\n## Input\n\nThe 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_.\n\n## Output\n\nOutput the answer to the problem modulo 109 + 7.\n\n[samples]\n\n## Note\n\nPermutations 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\\].","is_translate":false,"language":"English"}],"meta":{"iden":"CF886E","tags":["combinatorics","dp","math"],"sample_group":[["5 2","22"],["5 3","6"],["6 3","84"]],"created_at":"2026-03-03 11:00:39"}}