令 $\{a_1,a_2,\dots ,a_n\}$ 为长度为 $n$ 的整数序列，使得：

• $a_1=6$
• 对于所有 $1\le i<n$：$\varphi (a_i)<\varphi (a_{i+1})<a_i<a_{i+1}$。¹

设 $S(N)$ 为 $a_n\le N$ 的此类序列的数量。
例如，$S(10)=4$：$\{6\}$、$\{6,8\}$、$\{6,8,9\}$ 和 $\{6,10\}$。
我们可以验证 $S(100)=482073668$ 和 $S(10000)mod{10}^8=73808307$。

求 $S(20000000)mod{10}^8$。

¹ $\varphi$ 表示欧拉函数。