{a₁, a₂,..., a_n}는 길이 n의 정수 수열로 다음 조건을 만족합니다:

• a₁ = 6
• 모든 1 ≤ i < n에서 : φ(a_i) < φ(a_i+1) < a_i < a_i+1¹

S(N)은 a_n ≤ N인 수열의 개수입니다.
예를 들어, S(10) = 4 이고: 각 수열은 {6}, {6, 8}, {6, 8, 9}, {6, 10}입니다.
S(100) = 482073668이고 S(10 000) mod 10⁸ = 73808307 임을 확인할 수 있습니다.

S(20 000 000) mod 10⁸를 구하세요.

주)¹ φ 는 오일러 토션트(totient) 함수입니다.