2515: 密码
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
某保险箱的密码由一串奇怪的n个数字表示，其中第一个是0或1，第二个1或2，第三个是2或3……第n个是n-1或n。
为了传送密码不在传递中被泄露，某组织采用了这样一种方式：传送的信息是一个0至n的全排列，然后密码的第k位为传送的序列中k-1和k两个数字中靠前的一个。
比如：传送的是：3 0 1 2
密码就是：0 1 3
其中：第一位是0 和1 中靠前的数字0
第二位是1 和2 中靠前的数字1
第三位是2 和3 中靠前的数字3
现在为了测试这套系统的好坏，看看有多少排列对应的密码是一样的。
现给你一个密码序列，请你算出有多少全排列对应这个密码。
输入
输入有多组样例
每组样例第一行是一个数n（1<=n<1000）
接下来有n个数字，密码序列，数字间以空格隔开
输出
输出答案mod 1000007的值
样例输入 复制
1
1
2
0 2
样例输出 复制
1
2
提示
对于第一个样例，原序列只能是（1 0）一种
对于第二个样例，原序列可能是（0 2 1）（2 0 1）两种