题目描述

给定一个$\{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$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。