jmc

A positive integer $n$ has exactly two 1s in its binary representation exactly when $n=2^j+2^k$ for $j\ne k$ nonnegative integers. Thus, the set $S$ is equal to the set $\{n\in \mathbb{Z}\mid n=2^j+2^k\mathrm{and}0\le j<k\le 39\}$. (The second condition ensures simultaneously that $j\ne k$ and that each such number less than $2^{40}$ is counted exactly once.) This means there are $\left(\genfrac{}{}{0ex}{}{40}{2}\right)=780$ total such numbers. Now, consider the powers of $2$ mod $9$: $2^{6n}\equiv 1,2^{6n+1}\equiv 2,2^{6n+2}\equiv 4,2^{6n+3}\equiv 8\equiv -1,$ $2^{6n+4}\equiv 7\equiv -2,$ $2^{6n+5}\equiv 5\equiv -4(\mathrm{mod}9)$. It's clear what the pairs $j,k$ can look like. If one is of the form $6n$ (7 choices), the other must be of the form $6n+3$ (7 choices). If one is of the form $6n+1$ (7 choices) the other must be of the form $6n+4$ (6 choices). And if one is of the form $6n+2$ (7 choices), the other must be of the form $6n+5$ (6 choices). This means that there are $7\cdot 7+7\cdot 6+7\cdot 6=49+42+42=133$ total "good" numbers. The probability is $\frac{133}{780}$, and the answer is $133+780=\boxed{913}$.