序列$s_n$由$s_1=102022661$和$s_n=s_{n-1}^{2}mod998388889$为$n>1$定义。

让 $a_n=s_{2n-1}$ 和 $b_n=s_{2n}$ 为 $n=1,2,...$

定义一个 $N\times N$ 矩阵，其值为 $M_{i,j}=a_i+b_j$。

设 $A(N)$ 为从 $M_{1,1}$（左上）到 $M_{N,N}$（右下）的最小路径总和，其中每一步要么向右，要么向下。

您获得 $A(1)=966774091$、$A(2)=2388327490$ 和 $A(10)=13389278727$。

查找 $A({10}^7)$。