---

Problem 733

---

Ascending subsequences

Let $a_i$ be the sequence defined by $a_i=153^i \bmod 10\ 000\ 019$ for $i \ge 1$.
The first terms of $a_i$ are: $153, 23409, 3581577, 7980255, 976697, 9434375, \dots$

Consider the subsequences consisting of $4$ terms in ascending order. For the part of the sequence shown above, these are:
$153, 23409, 3581577, 7980255$
$153, 23409, 3581577, 9434375$
$153, 23409, 7980255, 9434375$
$153, 23409, 976697, 9434375$
$153, 3581577, 7980255, 9434375$ and
$23409, 3581577, 7980255, 9434375$.

Define $S(n)$ to be the sum of the terms for all such subsequences within the first $n$ terms of $a_i$. Thus $S(6)=94513710$.
You are given that $S(100)=4465488724217$.

Find $S(10^6)$ modulo $1\ 000\ 000\ 007$.

---

递增子序列

对于任意$i \ge 1$，序列$a_i$满足$a_i=153^i \bmod 10\ 000\ 019$。
该序列的一开始几项为：$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)$并对$1\ 000\ 000\ 007$取余。

---