We will count the number of bad permutations, at the end we subtract it from $$$n!$$$ (modular $$$n!$$$ is simple — if $$$n < m$$$, then we count head-on, otherwise we take it equal to $$$0$$$). We will add numbers to the permutation in order ($$$1, 2, ..., n$$$). If we add the number $$$i$$$, then we have $$$i$$$ insertion options, since there are $$$i - 1$$$ numbers in the permutation now. A pair of neighboring elements is called good if it meets the requirement from the statement ($$$x$$$ and $$$x + 1$$$). Now let $$$k$$$ be the number of good pairs in the permutation. If we insert $$$i$$$ between the indices of a good pair, then their number will decrease by $$$1$$$, if we insert it after the number $$$i - 1$$$, then it will increase by $$$1$$$, otherwise it will not change. This means that to increase the number of good pairs by $$$1$$$ we have a $$$1$$$ insertion option, to decrease by $$$1$$$ there are $$$k$$$ options, if we do not change anything there are $$$n - k - 1$$$ options. After $$$n$$$ insertions, we want to get the number of good pairs equal to $$$0$$$, so the increases and decreases are split into pairs. We want to find the number of all correct variants of insertions, if we do not have any increases this number is $$$(n - 1)!$$$ (from number of not changing options). Consider the first increase, let it be for the number $$$x$$$. Before it, there were $$$0$$$ pairs, so the number of permutations is equal to $$$(k - 2)!$$$ (according to the number of insertion options that do not change anything). We have a $$$1$$$ option for this insert. Note that for the next insertion (if it does not change) we will have $$$k - 1$$$ options, for the second after us there will be $$$k$$$ options, and so on, that is, we continued to accumulate the factorial. Consider a pairwise decrease (just this pair was removed), let it be at the moment $$$y$$$. We will only have the $$$1$$$ insert option since we are deleting a specific pair. Note that due to the presence of a pair (we assume that there is only one, for a larger number, the proof is obviously constructed in the same way, we only need to carefully take into account that there will be other deletions) before deleting it, we had $$$y - 3$$$ options on the previous insert, $$$1$$$ on the current one, and on the next there will already be $$$y$$$, that is, the factors $$$y - 2$$$ and $$$y - 1$$$ have been removed. We are looking for the sum over all variants of the remaining product after some set of deletions of pairs of consecutive numbers. Since before $$$ y $$$ there is a $$$ y - 1 $$$ number, and any of them could be paired with $$$ y $$$, then products without $$$y - 2$$$ and $$$y - 1$$$ will be counted $$$y - 1$$$ times, that is, we just removed $$$y - 2$$$. Thus, we have reduced the problem to the fact that we can remove any subset of factors from $$$(n - 1)!$$$, while we cannot remove two consecutive numbers (pairs $$$y - 2, y - 1$$$ cannot intersect in different $$$y$$$), you need to find the sum over all the products after deletions. This is easily done using DP ($$$dp_0 = dp_1 = 1$$$, $$$dp_i = dp_{i - 2} * (i - 1) + dp_{i - 1} * i $$$, the answer is $$$dp_{n - 1}$$$) in $$$O(n)$$$ and earns $$$77$$$ points. Now note that after $$$m$$$ the modulo remainders are looped. We will divide the old $$$dp$$$ into $$$dp1$$$ ($$$dp1_i$$$ — $$$i$$$ must be deleted) and $$$dp2$$$ ($$$dp2_i$$$ — $$$i$$$ can be deleted or not deleted), we will calculate the values of DP from $$$0$$$ to $$$m$$$. $$$dp1_i = dp2_{i - 2} * (i - 1) $$$, $$$dp2_i = dp2_{i - 1} * i + dp1_i$$$. Note that all terms in which one of $$$m, 2m, ...$$$ is not removed are equal to $$$0$$$ and do not affect the sum. It is not hard to prove that then the answer to the problem is $$$(dp1_m)^{\frac{n}{m}} * dp2_{n\pmod{m}}$$$. Using binary exponentiation, we get a $$$O(m + log_2(\frac{n}{m}))$$$ solution, which gains $$$100$$$ points. All formulas in the solution were required to be taken modulo $$$m$$$.
PS: My proof seems to me too complicated, it seems that ShinigamiCHOP has a simpler proof.
