AIME 2013b Problem 9

A $7\times 1$ board is completely covered by $m\times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the board. Each tile is either red, blue, or green. Let $N$ be the number of tilings of the $7\times 1$ board in which all three colors are used at least once. For example, a $1\times 1$ red tile followed by a $2\times 1$ green tile, a $1\times 1$ green tile, a $2\times 1$ blue tile, and a $1\times 1$ green tile is a valid tiling. Note that if the $2\times 1$ blue tile is replaced by two $1\times 1$ blue tiles, this results in a different tiling. Find the remainder when $N$ is divided by $1000$.