Answer: E

Solution:

Regard the five digits, in order, as the preferred parking spaces of five cars. Spaces are numbered $0,1,2,3,4,$ and each car takes its preferred space if possible, or else the first empty space to its right. If the preferences sorted into nondecreasing order are $b_1\le b_2\le\cdots\le b_5,$ all cars park exactly when $$b_i\le i-1\qquad(1\le i\le5).$$ These inequalities are precisely the conditions in the problem.

To count such preference strings, add a sixth space and arrange spaces $0,1,\ldots,5$ in a circle. For any of the $6^5$ preference strings, all five cars park and exactly one space remains empty. Rotating every preference by one position rotates the empty space as well. Thus each orbit of six preference strings has each possible empty space exactly once.

Therefore exactly $6^5/6=6^4=1296$ circular preference strings leave space $5$ empty. No car in such a string prefers space $5,$ and cutting the circle immediately after that empty space gives exactly a successful parking sequence on spaces $0$ through $4.$ Hence the desired number of strings is $1296.$

Thus, E is the correct answer.