733 : 昇順の部分列

$a_i$を、$i \geq 1$について$a_i = 153^i \mod 10\,000\,019$で定義される数列とする。 $a_i$は$153, 23409, 3581577, 7980255, 976697, 9434375, \dots$である。

4項からなる昇順の部分列を考えよう。上に示した部分に関してそのようなものは、 153, 23409, 3581577, 7980255 153, 23409, 3581577, 9434375 153, 23409, 976697, 9434375 153, 3581577, 7980255, 9434375 23409, 3581577, 7980255, 9434375 である。

$a_i$の最初の$n$項から得られるこのような昇順部分列の総和を$S(n)$とする。 すなわち$S(6) = 94513710$である。 また$S(100) = 4465488724217$である。

$S(10^6)$を$1\,000\,000\,007$で割った余りを答えよ。