Totient Stairstep Sequences

Let ${a_{1}, a_{2}, \dots, a_{n}}$ be an integer sequence of length $n$ such that:

$a_{1} = 6$
for all $1 \leq i < n$ : $ϕ (a_{i}) < ϕ (a_{i + 1}) < a_{i} < a_{i + 1}$ .¹

Let $S (N)$ be the number of such sequences with $a_{n} \leq N$ .
For example, $S (10) = 4$ : ${6}$ , ${6, 8}$ , ${6, 8, 9}$ and ${6, 10}$ .
We can verify that $S (100) = 482073668$ and $S (10 000) mod 10^{8} = 73808307$ .

Find $S (20 000 000) mod 10^{8}$ .

¹ $ϕ$ denotes Euler's totient function.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.