ZA-SAMO 2000 Problem 6

Let $A_n$ be the number of ways to tile a $4 \times n$ rectangle using $2 \times 1$ tiles. Prove that $A_n$ is divisible by 2 if and only if $A_n$ is divisible by 3.