At a recent math contest, Evan was asked to find $2^{2016} \pmod{p}$ for a given prime number $p$ with $100 < p < 500$. Evan has forgotten what the prime $p$ was, but still remembers how he solved it:

- Evan first tried taking $2016$ modulo $p - 1$, but got a value $e$ larger than $100$.
- However, Evan noted that $e - \frac{1}{2}(p - 1) = 21$, and then realized the answer was $-2^{21} \pmod{p}$.

What was the prime $p$?

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