2017 is prime

Relevant wiki: Wilson's Theorem

By Wilson's theorem, since 2017 is prime, $2016! \equiv -1 \pmod{2017}$ . If we let $2009! = x$ , then $2016! = x \cdot (2010 \cdot \ldots \cdot 2016)$ , so we just need to find $2010 \cdot \ldots \cdot 2016 \pmod{2017}$ .

This is not very difficult. We have $2010 \cdot \ldots \cdot 2016 \equiv (-7) \cdot \ldots \cdot (-1) \equiv -5040 \pmod{2017}$ . Thus $-1 \equiv -5040x \pmod{2017}$ .

Now, you might observe that 5040 is roughly 5/2 times 2017. In fact, $5040 \cdot 2 = 10080 = 2017 \cdot 5 - 5$ . Thus, multiplying both sides by 2 gives $-2 \equiv -10080x \equiv 5x \pmod{2017}$ .

Finally, finding the inverse of 5 mod 2017 isn't too difficult; you only need to check 4 candidates. (The candidates are the first multiple of 5 after some multiple of 2017; namely, 2020 (after 2017), 4035 (after 4034), 6055 (after 6051), and 8070 (after 8068).) We see that $5 \cdot 807 = 4035 = 2017 \cdot 2 + 1$ , so the inverse is 807. Thus we obtain $x \equiv -2 \cdot 807 \equiv -1614 \equiv \boxed{403} \pmod{2017}$ .