Пусть {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⁸.

¹ φ обозначена фи-функция Эйлера.