令 $a_i$ 为 $a_i={153}^{i}mod10000019$ 为 $i\ge 1$ 定义的序列。
$a_i$ 的第一项是： $153,23409,3581577,7980255,976697,9434375,\dots$

考虑由 $4$ 项按升序排列组成的子序列。对于上面显示的序列部分，这些是：
$153,23409,3581577,7980255$
$153,23409,3581577,9434375$
$153,23409,7980255,9434375$
$153,23409,976697,9434375$
$153,3581577,7980255,9434375$ 和
$23409,3581577,7980255,9434375$。

将 $S(n)$ 定义为 $a_i$ 的第一个 $n$ 项中所有此类子序列的项之和。因此$S(6)=94513710$。
您已获得 $S(100)=4465488724217$。

求 $S({10}^6)$ 对 $1000000007$ 求模。