We define $N$ as the set of natural numbers $n < 10^6$ with the following property: There exists an integer exponent $k$ with $1 \leq k \leq 43$, such that $2012 \mid n^k - 1$. Find $|N|$.

Let's think step by step and output the final answer within \boxed{}.
user