Calculate the value of an expression with large numbers, how?

Question

Algorithms

An integer N is given. Calculate the following expression: (1^N + 2^N + 3^N + 4^N) mod 5,
where 0 <= N <= 10^100000
The program should not run for more than 0.2 seconds.

Answer 1

(1 ^N + 2 ^N + 3 ^N + 4 ^N ) mod 5 = (1 + 2 ^{N mod 4} + 3 ^{N mod 4} + 4 ^{N mod 4} ) mod 5