What are the last four digits in the binary expansion $1234^{5555} + 4321^{5555}$?

I'm having a lot of trouble figuring out this discrete math question:

What are the last four bits in the binary expansion of 1234^5555 + 4321 ^5555?


I need to add the two numbers and convert to binary. From what I know so far, to get the last bit from binary, you need to take mod 2. From this, to get the last four bits I understand that you need to take mod 16. However, I don't know how to efficiently take a mod of a very large number or convert a large number to binary.

I've also considered using Fermat's Little Theorem.

Can someone help me out or guide me along the right path?

-

$a^m \equiv b^m$ if $a \equiv b$. Thus, $1234^{5555} \equiv 2^{5555}$, which is definitely divisible by 16, so equal to 0 mod 16.

Now, what is 4321 mod 16? What is it when taken to power 5555?

-
First, consider $4321$ and $1234$ modulo $16$:
1. $4000 \equiv 320 \equiv 0 \pmod{16}$, so $4321 \equiv 1 \pmod{16}$.
2. $1200 \equiv 32 \equiv 0 \pmod{16}$, so $1234 \equiv 2 \pmod{16}$.
Finally, $1^{5555} \equiv 1 \pmod{16}$ and $2^{5555} \equiv 16 \cdot 2^{5551} \equiv 0 \pmod{16}$, so their sum is $1 \pmod{16}$, or $\ldots0001_2$ in binary form.