---

Problem 733

---

Ascending subsequences

Let $a_i$ be the sequence defined by $a_i={153}^{i}mod10000019$ 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 $1000000007$.

---

递增子序列

对于任意$i\ge 1$，序列$a_i$满足$a_i={153}^{i}mod10000019$。
该序列的一开始几项为：$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$取余。

---