对于所有 $k>0$，方程 $x^y=y^x$ 的正积分解为 $(2,4)$、$(4,2)$ 和 $(k,k)$。

对于给定的正整数 $n$，令 $f(n)$ 为整数值 $0<x,y\le n^2-n$ 的数量，使得 $$x^y\equiv y^x(\mathrm{mod}n).$$ 例如，$f(5)=104$ 和 $f(97)=1614336$。

令 $S(M,N)=\sum f(p)$ 的总和取自满足 $M\le p\le N$ 的所有质数 $p$。

您获得 $S(1,{10}^2)=7381000$ 和 $S(1,{10}^5)\equiv 701331986(\mathrm{mod}993353399)$。

查找 $S({10}^{16},{10}^{16}+{10}^6)$。以 $993353399$ 为模给出答案。