交换

【题目描述】

给定一个$\{0, 1, 2, 3, … , n - 1\}$的排列 $p$。一个$\{0, 1, 2 , … , n - 2\}$的排列$q$被认为是优美的排列，当且仅当$q$满足下列条件： 对排列$s =\{0, 1, 2, 3, ..., n - 1\}$进行$n–1$次交换。 ①交换$s[q_0],s[q_0 + 1]$。 ②交换$s[q_1],s[q_1 + 1]$。 …… 最后能使得排列$s = p$。 问有多少个优美的排列，答案对$10^9+7$取模。

【输入】

第一行一个正整数$n$。 第二行$n$个整数代表排列$p$。

【输出】

仅一行表示答案。

【输入样例】

3
1 2 0

【输出样例】

1

【提示】

【样例解释】 $q = \{0,1\}\{0,1,2\} →\{1,0,2\} → \{1, 2, 0\}$ $q = \{1,0\} \{0,1,2\} →\{0,2,1\} → \{2, 0, 1\}$ 【数据规模】 对于30%的数据，$n≤10$。 对于100%的数据，$n≤50$。