Fast Calculate

If $N=1$, the inner sum is empty, so the answer is $0$. Assume $N\geq 2$ below.

For a fixed $d$, define

$$H_d=\sum_{1\leq i<j\leq N}(d-1)^{i-1}d^{j-i-1}(d+1)^{N-j}.$$

Let $x=i-1$, $y=j-i-1$, and $z=N-j$. Then $x,y,z$ are nonnegative integers satisfying $x+y+z=N-2$, hence

$$H_d=\sum_{x+y+z=N-2}(d-1)^x d^y(d+1)^z.$$

For three distinct values $a,b,c$,

$$\sum_{x+y+z=k}a^x b^y c^z = \frac{a^{k+2}}{(a-b)(a-c)} + \frac{b^{k+2}}{(b-a)(b-c)} + \frac{c^{k+2}}{(c-a)(c-b)}.$$

Substituting $a=d-1$, $b=d$, $c=d+1$, and $k=N-2$ gives

$$H_d=\frac{(d-1)^N-2d^N+(d+1)^N}{2}.$$

Let $f_d=d^N$. Twice the required value is

$$\sum_{d=1}^{M-1}(M-d)(f_{d-1}-2f_d+f_{d+1}).$$

After collecting the coefficient of each $f_k$, every coefficient for $2\leq k\leq M-1$ cancels, and only $f_M-Mf_1$ remains. Since $f_1=1$, the original expression equals

$$\frac{M^N-M}{2}.$$

Compute $M^N$ by binary exponentiation and multiply by the modular inverse of $2$, which is $499\,122\,177$ modulo $998\,244\,353$.

The time complexity is $O(\log N)$ and the memory complexity is $O(1)$.

Solution written by GPT5.6