2006 AIME I Problem 11

A collection of 8 cubes consists of one cube with edge-length k for each integer k, 1 \leq k \leq 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 that can be constructed. What is the remainder when T is divided by 1000 ?