Tot(ient)ally Cool!

The problem is equivalent to finding $109^{2017} \text{ mod }2^4$ .

$\begin{aligned} 109^{2017} & \equiv 109^{\color{#3D99F6}2017 \text{ mod }\phi(16)} \text{ (mod 16)} & \small \color{#3D99F6} \text{Since }\gcd(109, 16)=1 \text{, Euler's theorem applies.} \\ & \equiv 109^{\color{#3D99F6}2017 \text{ mod }8} \text{ (mod 16)} & \small \color{#3D99F6} \text{Euler's totient function } \phi (16) = 8 \\ & \equiv 109^{\color{#3D99F6}1} \text{ (mod 16)} \\ & \equiv 13_{10} \text{ (mod 16\_{10})} \\ & \equiv \boxed{1101}_2 \text{ (mod }10000_2) \end{aligned}$

To solve we can take this in modulo 16 because the last 4 digits in binary only go up to 8. This give us $13^{2017}$ . By Euler's Totient Formula, this is equivalent to 13. This in binary is 1101