Problem 619

Square subsets

For a set of positive integers $a, a + 1, a + 2, \dots, b$ , let $C (a, b)$ be the number of non-empty subsets in which the product of all elements is a perfect square.

For example $C (5, 10) = 3$ , since the products of all elements of $5, 8, 10$ , $5, 8, 9, 10$ and $9$ are perfect squares, and no other subsets of $5, 6, 7, 8, 9, 10$ have this property.

You are given that $C (40, 55) = 15$ , and $C (1000, 1234) mod 1000000007 = 975523611$ .

Find $C (1000000, 1234567) mod 1000000007$ .

平方子集

对于正整数集 $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) mod 1000000007 = 975523611$ 。

求 $C (1000000, 1234567) mod 1000000007$ 。