Рассмотрим смеси трех веществ: A, B и C. Смесь можно описать пропорцией количеств веществ A, B и C в ней, т.е. (a : b : c). Например, смесь, заданная пропорцией (2 : 3 : 5), содержит 20% A, 30% B и 50% C.

В рамках этой задачи мы не можем разделить смесь на отдельные компоненты. Однако, мы можем смешивать разные количества различных смесей, чтобы создать смесь с другой пропорцией.

Например: скажем, у нас есть три смеси с пропорциями (3 : 0 : 2), (3 : 6 : 11) и (3 : 3 : 4). Смешав 10 единиц первой, 20 единиц второй и 30 единиц третьей, мы получим новую смесь с пропорцией (6 : 5 : 9), так как:
(10·³/₅ + 20·³/₂₀ + 30·³/₁₀ : 10·⁰/₅ + 20·⁶/₂₀ + 30·³/₁₀ : 10·²/₅ + 20·¹¹/₂₀ + 30·⁴/₁₀) = (18 : 15 : 27) = (6 : 5 : 9)

Однако, из тех же трех смесей невозможно создать смесь с пропорцией (3 : 2 : 1), так как количество B всегда будет меньше количества C.

Пусть n будет натуральным числом. Предположим, что для каждой тройки целых чисел (a, b, c) при 0 ≤ a, b, c ≤ n и НОД(a, b, c) = 1, мы имеем смесь с пропорцией (a : b : c). Пусть M(n) будет множестваом всех таких смесей.

Например, M(2) содержит 19 смесей со следующими пропорциями:
{(0 : 0 : 1), (0 : 1 : 0), (0 : 1 : 1), (0 : 1 : 2), (0 : 2 : 1),
(1 : 0 : 0), (1 : 0 : 1), (1 : 0 : 2), (1 : 1 : 0), (1 : 1 : 1),
(1 : 1 : 2), (1 : 2 : 0), (1 : 2 : 1), (1 : 2 : 2), (2 : 0 : 1),
(2 : 1 : 0), (2 : 1 : 1), (2 : 1 : 2), (2 : 2 : 1)}.

Пусть E(n) будет количеством подмножеств M(n), которые могут произвести смесь с пропорцией (1 : 1 : 1), т.е. смесь с равными частями A, B и C.
Можно показать, что E(1) = 103, E(2) = 520447, E(10) mod 11⁸ = 82608406 и E(500) mod 11⁸ = 13801403.
Найдите E(10 000 000) mod 11⁸.