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,\ldots,n\} with |A|=|B|. For example, S_2 = 4 because the sum is taken over the pairs of subsets (A,B) \in \left\{(\emptyset,\emptyset),(\{1\},\{1\}),(\{1\},\{2\}),(\{2\},\{1\}),(\{2\},\{2\}),(\{1,2\},\{1,2\})\right\}, 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.

Leading zeroes must be inputted, so if your answer is 34, then input 034

Full credit goes to MAA for authoring these problems. These problems were taken on the AOPS website.