Project Euler Problem 635
Let Aq(n) be the number of subsets, B, of the set 1, 2, ..., q cdot n that satisfy two conditions: 1) B has exactly n el
Solution
Answer: 689294705
Using a roots-of-unity filter, for a prime $p$ and fixed $q$, we get
$$A_q(p)=\frac1p\sum_{j=0}^{p-1}[x^p]\prod_{r=0}^{p-1}(1+x\omega^{jr})^q.$$
For $p>q$, every nonzero $j$ permutes the $p$-th roots of unity, so
$$\prod_{r=0}^{p-1}(1+x\omega^{jr}) = 1+x^p,$$
hence
$$A_q(p)=\frac{1}{p}\left(\binom{qp}{p}+(p-1)q\right).$$
This reproduces the examples:
$$A_2(5)=\frac{1}{5}(252+8)=52, \qquad A_3(5)=\frac{1}{5}(3003+12)=603.$$
Therefore
$$S_2(L)=\sum_{p\le L}\frac{\binom{2p}{p}+2(p-1)}{p},$$
$$S_3(L)=\sum_{p\le L}\frac{\binom{3p}{p}+3(p-1)}{p},$$
with the lone exceptional case $A_2(2)=2$.
Evaluating these sums modulo $1,000,000,009$ for all primes $p\le 10^8$ gives:
$$S_2(10^8)+S_3(10^8)\equiv 867009142 \pmod{1,000,000,009}.$$
Answer: 867009142