(noch nicht übersetzt)

The sequence $s_n$ is defined by $s_1 = 102022661$ and $s_n = s_{n-1}^2 \bmod {998388889}$ 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)$.