---

Problem 635

---

Subset sums

Let $A_q(n)$ be the number of subsets, $B$, of the set $1,2,\dots ,q\cdot n$ that satisfy two conditions:

1) $B$ has exactly $n$ elements;
2) the sum of the elements of $B$ is divisible by $n$.

E.g. $A_2(5)=52$ and $A_3(5)=603$.

Let $S_q(L)$ be $\sum A_q(p)$ where the sum is taken over all primes $p\le L$.
E.g. $S_2(10)=554$, $S_2(100)\mathrm{mod}1000000009=100433628$ and $S_3(100)\mathrm{mod}1000000009=855618282$.

Find $S_2({10}^8)+S_3({10}^8)$. Give your answer modulo $1000000009$.

---

子集和

考虑集合$1,2,\dots ,q\cdot n$的子集$B$，且$B$满足以下两个条件：

1) $B$中恰好有$n$个元素；
2) $B$中元素的和能够被$n$整除；
记所有此类子集$B$的数目为$A_q(n)$。

例如，$A_2(5)=52$，$A_3(5)=603$。

记$S_q(L)$为$\sum A_q(p)$，其中$p$取遍所有满足$p\le L$的质数。
例如，$S_2(10)=554$，$S_2(100)\mathrm{mod}1000000009=100433628$，$S_3(100)\mathrm{mod}1000000009=855618282$。

求$S_2({10}^8)+S_3({10}^8)$，并将答案对$1000000009$取余。

---