Problem

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.