793 : 積の中央値

$S_i$ を次の擬似乱数生成器が生成する整数列とする。

• $S_0 = 290797$

• $S_{i+1} = {S_i} ^2 \bmod 50515093$

$M(n)$ を $0 \le i \lt j \lt n$ についての2つ組の積 $S_i S_j$ の中央値とする。 $M(3) = 3878983057768$ , $M(103) = 492700616748525$ である。

$M(1\,000\,003)$ を求めよ。