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.

Leading zeroes must be inputted, so if your answer is 34, then input 034

Full credit goes to MAA for authoring these problems. These problems were taken on the AOPS website.