2006 AIME I Problem 11

A collection of 8 cubes consists of one cube with edge-length k for each integer k, 1 \le k \le 8. A tower is to be built using all 8 cubes according to the rules:

- Any cube may be the bottom cube in the tower.

- The cube immediately on top of a cube with edge-length k must have edge-length at most k+2.

Let T be the number of different towers than can be constructed. What is the remainder when T 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.