一个关于错位排列的问题

对于一个排列 $a_n$，其元素为 $1,2,3,4,...,n$，如果它满足：

以上两个条件，我们就认为这个排列是合法的，现在，给定一个正整数 $M$，当 $n=M$ 时，合法排列有多少种，其中 $M\in[1,1000]$ 且 $M\in \mathbb {N}$