Problem 917

Minimal Path Using Additive Cost

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

Let $a_{n} = s_{2 n - 1}$ and $b_{n} = s_{2 n}$ for $n = 1, 2, \dots$

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})$ .

序列 $s_{n}$ 的定义为： $s_{1} = 102022661$ ；对于 $n > 1$ ， $s_{n} = s_{n - 1}^{2} mod 998388889$ 。

对于 $n = 1, 2, \dots$ ，令 $a_{n} = s_{2 n - 1}$ ， $b_{n} = s_{2 n}$ 。

考虑一个 $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})$ 。