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 {( nothing , nothing ) , ( { 1 } , { 1 } ) , ( { 1 } , { 2 } ) , ( { 2 } , { 1 } ) , ( { 2 } , { 2 } ) , ( { 1 , 2 } , { 1 , 2 } )} , \)
giving \(S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4 .\) Let
\(\dfrac{S_2022}{S_2021} = \dfrac{p}{q} ,\) where \(p\) and \(q\) are relatively prime
positive integers. Find the remainder when \(p + q\) is divided by
\(1000 .\)