$$\begin{aligned} N^2 &= (a_i\gt a_{i+1} を満たす iの個数)\times (a_j\gt a_{j+1} を満たす jの個数)\\\\
&=(a_i\gt a_{i+1} および a_j\gt a_{j+1}を満たす i,j の個数)
\end{aligned}$$

であるから，$a_i\gt a_{i+1}$ および $a_j\gt a_{j+1}$ を満たすような置換 $\\{a_n\\}$ の個数を $S_{i,j}$ とすると，
$$M=\dfrac{1}{1000!}\left(\sum_{1\leq i,j \leq 999}S_{i,j}\right)$$が成り立つ．これと
$$S_{i,j}=\left\\{
\begin{aligned} 
\dfrac{1000!}{2}&　(|i-j|=0のとき)\\\\
\dfrac{1000!}{6}&　(|i-j|=1のとき) \\\\
\dfrac{1000!}{4}&　(|i-j|\geq 2のとき)
\end{aligned}
\right.$$
より，
$$\begin{aligned}
M &=\dfrac{1}{1000!}\left(\dfrac{1000!}{2}\times999+\dfrac{1000!}{6}\times998\times2+\dfrac{1000!}{4}\times(999\times998-998\times2)\right)\\\\
&=\dfrac{748751}{3}
\end{aligned}$$
となり，解答すべき値は $\bf 748754$ である．
公式解説
https://onlinemathcontest.com/contests/omc120/editorial/4779
　$1000!$ 通りある置換が同様に確からしい確率で起きると仮定して，$N^2$ の期待値を求める．\
　任意の $i$ に対して，確率変数 $x_i$ を次のように定める：

- $a_i \gt a_{i+1}$ であれば $x_i=1$，そうでなければ $x_i=0$．

　$x_i$ と $x_j$ は基本的には独立であるが，$a_i \gt a_{i+1} \gt a_{i+2}$ である確率は $\dfrac{1}{6}$ であることに注意しなければならない．以下，期待値は $E(*)$ で表す．\
$$\begin{aligned}
E(N^2)=E(\left( \sum\limits_{i=1}^{999} x_i \right)^2) &= \sum\limits_{i=1}^{999} E(x_i^2)+\sum\limits_{|i-j|=1} E(x_i x_j)+\sum\limits_{|i-j| \geq 2} E(x_i x_j)\\\\
&=999×\dfrac{1}{2}+998×2×\dfrac{1}{6}+(999×998-998×2)×\dfrac{1}{4}
\end{aligned}$$
となって，公式解説と同じ式を得る．
期待値の性質を用いる方法
https://onlinemathcontest.com/contests/omc120/editorial/4779/441
　$1,2,3,\ldots,1000$ の置換 $a_1,a_2,\ldots,a_{1000}$ について，$a_i\gt a_{i+1}$ をみたす $999$ 以下の正整数 $i$ の個数を $N$ とします．$1000!$ 通りある置換すべてについて， $N^2$ の（相加）平均 $M$ を求めてください．ただし，$M$ は互いに素な正整数 $a,b$ を用いて $\dfrac{a}{b}$ と表せるので，$a+b$ を解答してください．