【题目描述】

给定一个{0, 1, 2, 3, … , n - 1}的排列 p。一个{0, 1, 2 , … , n - 2}的排列q被认为是优美的排列，当且仅当q满足下列条件：

对排列s = {0, 1, 2, 3, ..., n - 1}进行n – 1次交换。

1. 交换s[q0],s[q0 + 1]

2. 交换s[q1],s[q1 + 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