Пусть $a_i$ будет последовательностью, определенной как $a_i=153^i \bmod 10\,000\,019$ для $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)$ как сумму элементов для всех таких подпоследовательностей среди первых $n$ элементов последовательности $a_i$. Таким образом, $S(6)=94513710$.
Известно, что $S(100)=4465488724217$.

Найдите остаток от деления $S(10^6)$ на $1\,000\,000\,007$.