337 : トーティエント階段数列

$\{a_1, a_2,\dots, a_n\}$を次のような長さ$n$の 整数列とする.

• $a_1 = 6$

• $1 \leq i < n$に対し : $φ(a_i) < φ(a_{i+1}) < a_i < a_{i+1}$

$a_n \leq N$となる数列の数を$S(N)$とする. 例えば$S(10) = 4$である：{6}, {6, 8}, {6, 8, 9}, {6, 10}. $S(100) = 482073668$と$S(10\, 000) \mod 10^8 = 73808307$であることが確かめられる.

$S(20\, 000\, 000) \mod 10^8$を求めよ.

注：$φ$はオイラーのトーティエント関数を表す.