Spatial Awareness

Usually, in data processing multidimensional data (i.e. a multidimensional array) is vectorized and then processed. However, because of vectorization the spatial information in the data is lost.

For this problem, assume that you receive $1000$ distinct values after a vectorization of a $4D$ array and you have no other information whatsoever. Then, how many possible spatial states are there for the original data? Give your answer in $mod$ $100000009$

Note: Assume that an array of size $1\times 1\times 1\times 1000$ or any other combination involving $1$, will also count as a $4D$ array.