2004 AIME II Problem 10

Let \mathcal{S} be the set of integers between 1 and 2^{40} whose binary expansions have exactly two 1's. If a number is chosen at random from \mathcal{S}, the probability that it is divisible by 9 is p / q, where p and q are relatively prime positive integers. Find p+q.