Counting subsets

For any positive integer $M$ , consider the polynomial $F(X) \; = \; \prod_{j=1}^{5M}(1 + X^j) \; = \; \sum_{k=0}^{\frac52M(5M+1)}a_kX^k$ where $a_k$ is the number of subsets of $\{1,2,3,\ldots,5M\}$ whose total is equal to $k$ . Thus we want to calculate $S \; = \; \sum_{k=0}^M a_{5k} \; = \; \tfrac15\sum_{k=0}^4 F(\zeta^k)$ where $\zeta = e^{\frac{2\pi i}{5}}$ is a primitive fifth root of unity. Now $F(\zeta^k) \; = \; \prod_{j=1}^{5M}(1 + \zeta^{jk}) \; = \; \left(\prod_{j=1}^5(1 + \zeta^{jk})\right)^M$ and so $F(\zeta^0) \; = \; 2^{5M}$ , while $F(\zeta^k) \; =\; F(\zeta) \; = \; \left(-\prod_{j=1}^5(-1 - \zeta^j)\right)^M \; = \; \left(-\big((-1)^5 - 1\big)\right)^M \; = \; 2^M$ for each $1 \le k \le 4$ . Thus $S \; = \; \tfrac15\big(2^{5M} + 4\times 2^M\big) \; =\; \tfrac15\big(2^{5M} + 2^{M+2}\big)$ It is worth noting that $2^4 \equiv 1 \pmod{5}$ , so that $2^5 \equiv 2 \pmod{5}$ , and hence $2^{5M} \equiv 2^M \pmod{5}$ , so that $2^{5M} + 2^{M+2} \equiv 2^M + 2^{M+2} \equiv (1 + 4)2^M \equiv 0 \pmod{5}$ , and hence this formula for $S$ does always give us an integer, whatever the value of $M$ .

In this case we have $M=400$ , so that $n+m+k = 5 + 2000 +402 = \boxed{2407}$ .