Задача 619
Квадратные подмножества

Для множества положительных целых чисел $\{a, a+1, a+2, \dots , b\}$ пусть $C(a,b)$ будет количеством непустых подмножеств, в которых произведение всех элементов является полным квадратом.

Например, $C(5,10)=3$, так как произведения всех элементов подмножеств $\{5, 8, 10\}$, $\{5, 8, 9, 10\}$ и $\{9\}$ являются полными квадратами, и никакие другие подмножества $\{5, 6, 7, 8, 9, 10\}$ таким свойством не обладают.

Известно, что $C(40,55) =15$ и $C(1000,1234) \text{ mod } 1000000007=975523611$.

Найдите $C(1000000,1234567) \text{ mod } 1000000007$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net