2016 Fermat Problem 25

The set A = \{1, 2, 3, \ldots, 2044, 2045\} contains 2045 elements. A subset S of A is called *triple-free* if no element of S equals three times another element of S. For example, \{1, 2, 4, 5, 10, 2043\} is triple-free, but \{1, 2, 4, 5, 10, 681, 2043\} is not triple-free. The triple-free subsets of A that contain the largest number of elements contain exactly 1535 elements. There are n triple-free subsets of A that contain exactly 1535 elements. The integer n can be written in the form p^a q^b, where p and q are distinct prime numbers and a and b are positive integers. If N = p^2 + q^2 + a^2 + b^2, then the last three digits of N are

\textbf{(A)}\ 202\quad \textbf{(B)}\ 102\quad \textbf{(C)}\ 302\quad \textbf{(D)}\ 402\quad \textbf{(E)}\ 502

If there are no answer choices shown, enter a numerical answer.

Full credit to this problem is given to the CEMC, you may view all Fermat contests here.