elementary number theory - Find remainder when $777^{777}$ is divided by $16$

Find remainder when $777^{777}$ is divided by $16$.

$777=48\times 16+9$. Then $777\equiv 9 \pmod{16}$.

Also by Fermat's theorem, $777^{16-1}\equiv 1 \pmod{16}$ i.e $777^{15}\equiv 1 \pmod{16}$.

Also $777=51\times 15+4$. Therefore,

$777^{777}=777^{51\times 15+4}={(777^{15})}^{51}\cdot777^4\equiv 1^{15}\cdot 9^4 \pmod{16}$ leading to $81\cdot81 \pmod{16} \equiv 1 \pmod{16}$.

But answer given for this question is $9$. Please suggest.