822 : 最小を二乗

リストは最初に数 $2, 3, \dots, n$ からなる。 ラウンドごとに、リスト中の最小の数をその二乗に置き換える。 最小の数が複数個ある場合は、そのうちの一つだけを置き換える。

例として、 $n=5$ の最初の3ラウンドを示す： $[2,3,4,5] \xrightarrow{(1)} [4,3,4,5] \xrightarrow{(2)} [4,9,4,5] \xrightarrow{(3)} [16,9,4,5]$

$m$ ラウンド後のリストの全ての数の和を $S(n,m)$ としよう。 例えば、$S(5,3) = 16 + 9 + 4 + 5 = 34$ である。 また $S(10, 100) \equiv 845339386 \pmod{1234567891}$ である。

$S(10^4, 10^{16}) \bmod 1234567891$ を求めよ。