The sequence $s_n$ is defined by $s_1=102022661$ and $s_n=s_{n-1}^{2}mod998388889$ for $n>1$.

Let $a_n=s_{2n-1}$ and $b_n=s_{2n}$ for $n=1,2,...$

Define an $N\times N$ matrix whose values are $M_{i,j}=a_i+b_j$.

Let $A(N)$ be the minimal path sum from $M_{1,1}$ (top left) to $M_{N,N}$ (bottom right), where each step is either right or down.

You are given $A(1)=966774091$, $A(2)=2388327490$ and $A(10)=13389278727$.

Find $A({10}^7)$.