站外题求助

【问题描述】

给定一个{0, 1, 2, 3, … , n - 1}的排列 p

注意给定的p可以不是由小到大排列，但一定是0~n-1的n个不相同的数

对于一个包含{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取模。

题意简述：对于固定排列顺序的s={0, 1, 2, 3, ..., n - 1}，问有多少种排列q，可以将s按上述方式进行n-1次变换后，变为指定输入的排列p。

【输入格式】

第一行一个正整数n

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

【输出格式】

仅一行表示答案。

【样例1】

输入数据 1

3 1 2 0

输出数据 1 1

【样例1解释】 q = {0,1} 时

交换结果依次为：{0,1,2} ->{1,0,2} -> {1,2,0}，使得{0,1,2}变为了指定的{1,2,0}

q = {1,0} 时

交换结果依次为：{0,1,2} ->{0,2,1} -> {2,0,1}，不能变为指定的排列p

【数据范围】

对于 30%的数据，n <= 10

对于 100%的数据，n <= 50