Let $a_0, a_1, \dots$ be an integer sequence defined by:

• $a_0 = 1$;
• for $n \ge 1$, $a_n$ is the sum of the digits of all preceding terms.

The sequence starts with $1, 1, 2, 4, 8, 16, 23, 28, 38, 49, \dots$
You are given $a_{10^6} = 31054319$.

Find $a_{10^{15}}$.