Answer: 913

Solution:

The set $\mathcal{S}$ consists of the $\binom{40}{2} = 780$ numbers $2^a + 2^b$ with $0 \le a \lt b \le 39.$ Since $2^a$ is coprime to $9,$ we have $9 \mid 2^a(2^{b-a} + 1)$ exactly when $2^{b-a} \equiv -1 \pmod{9}.$ The powers of $2$ modulo $9$ cycle through $2, 4, 8, 7, 5, 1$ with period $6,$ so $2^d \equiv 8 \equiv -1$ exactly when $d \equiv 3 \pmod{6}.$

For each difference $d = b - a$ there are $40 - d$ pairs, so the number of multiples of $9$ in $\mathcal{S}$ is $$\begin{aligned} &\sum_{d = 3, 9, \ldots, 39} (40 - d) \\ &= 37 + 31 + 25 \\ &\quad {}+ 19 + 13 + 7 + 1 \\ &= 133. \end{aligned}$$

The probability is $\frac{133}{780},$ and since $133 = 7 \cdot 19$ while $780 = 2^2 \cdot 3 \cdot 5 \cdot 13,$ it is in lowest terms. Thus $p + q = 133 + 780 = 913.$