2022 AIME I Problem 12

For any finite set X, let |X| denote the number of elements in X. Define

S_{n}=\sum|A \cap B|

where the sum is taken over all ordered pairs (A, B) such that A and B are subsets of \{1,2,3, \cdots, n\} with |A|=|B|. For example, S_{2}=4 because the sum is taken over the pairs of subsets

(A, B) \in\{(\emptyset, \emptyset),(\{1\},\{1\}),(\{1\},\{2\}),(\{2\},\{1\}),(\{2\},\{2\}),(\{1,2\},\{1,2\})\}

giving S_{2}=0+1+0+0+1+2=4. Let \frac{S_{2022}}{S_{2021}}=\frac{p}{q}, where p and q are relatively prime positive integers. Find the remainder when p+q is divided by 1000 .