2013 AIME II 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 .