Once there was a 9

The sum of the first four binomial coefficients equals $\frac{(n+1)(n^2-n+6)}6.$ So $(n+1)(n^2-n+6) | 3 \cdot 2^{2009}.$ There are two cases.

Case 1: $n+1 = 2^a$ for some $a.$ Then $n^2-n+6 = 2^{2a} - 3 \cdot 2^a + 8.$ This is either a power of $2$ or $3$ times a power of $2.$

Let $x = 2^a.$ Then I claim that for $x > 8,$ $\frac34 x^2 < x^2-3x+8 < \frac32 x^2.$ This is an easy algebra exercise, left to the reader. But this means that $2^{2a}-3\cdot 2^a + 8$ is strictly between $3 \cdot 2^{2a-2}$ and $3 \cdot 2^{2a-1},$ so it can't be $3$ times a power of $2$ if $a > 3.$

Similarly, $\frac12 x^2 < x^2 -3x+8 < x^2$ for $x > 8,$ so $2^{2a}-3\cdot 2^a + 8$ is strictly between $2^{2a-1}$ and $2^{2a},$ so it can't be a power of $2$ if $a > 3.$

That reduces the possible values of $a$ to $a = 0,1,2,3.$ Checking directly, we see that $a = 1,2,3$ give the solutions $n=1,3,7$ respectively.

Case 2: $n+1 = 3 \cdot 2^a$ for some $a.$ Then $n^2-n+6 = 9 \cdot 2^{2a} - 9 \cdot 2^a + 8.$ This is supposed to be a power of $2.$ Again, let $x = 2^a.$ This time I claim that for $x > 8,$ $8x^2 < 9x^2-9x+8 < 16x^2.$ So $9 \cdot 2^{2a} - 9 \cdot 2^a + 8$ is strictly between $2^{2a+3}$ and $2^{2a+4},$ so can't be a power of $2$ if $a > 3.$ As before, we have only the four cases $a=0,1,2,3$ to check. Here $a=0,3$ lead to the solutions $n=2,23$ respectively.

So the answer is $1+3+7+2+23 = \fbox{36}.$