問題敘述
資工系宿營今年有N位隊員參加，每位隊員在報名時都會獲得一個介於1 ~ N 之間的編號，隊員的編號彼此相異。宿營過程中他們會入住兩間旅館，每位隊員都住在旅館內的單人房內。 為了增添趣味，在第一天入住旅館時帶隊老師請隊員們用任意順序排成一列隊伍，從隊伍最前方的隊員開始使用以下的規則依序領取房卡： ‧一開始先嘗試領取1號房間的房卡。如果試圖領取的房卡已被某位隊員拿走，則重複套用以下的規則直到自己領取到一張房卡為止。 ‧如果第 x 號房間的房卡已被拿走，且自己的編號比拿走該房卡的隊員編號小，則接下來嘗試領取2x號房間的房卡。 ‧如果第 x 號房間的房卡已被拿走，且自己的編號比拿走該房卡的隊員編號大，則接下來嘗試領取2x+1號房間的房卡。 過了兩天，隊員們要換一間旅館住宿，帶隊老師請隊員們再使用相同的方式領取房卡入住。領取完房卡後，老師驚訝地發現所有隊員都住在與兩天前號碼相同的房間！他很好奇發生這件事的可能性有多大，請你寫一支程式幫忙計算有多少種隊員領取房卡的順序可以使每位隊員都領到相同號碼房間的房卡。由於答案的數字可能很大，請輸出可能的方法數除以 (109+7) 的餘數。
輸入格式
第一列有一個正整數N (3 ≤ N ≤ 103)，代表參與宿營的隊員數。 第二列有N個整數 Pi (1 ≤ i ≤ N , 1 ≤ Pi ≤ N )，代表第一天第 i 個領取房卡的隊員編號是 Pi 。所有隊員編號都是相異的。
輸出格式 請輸出一個整數，代表能使所有隊員住進相同房間的方法數除以 (109+7) 的餘數。
輸入範例1
5
1 2 4 5 3
輸出範例1
2
輸入範例1的說明：在第一天編號為1, 2, 3, 4, 5號的隊員分別會領到1, 3, 14, 7, 15號房間的房卡。在120種排列的可能性中，只有 [1, 2, 4, 5, 3] 和 [1, 2, 4, 3, 5] 兩種隊伍排列可以使得每個人都拿到這個號碼的房卡。
輸入範例2
10
7 8 9 10 1 2 3 4 5 6
輸出範例2
84
輸入範例3
12
7 3 5 10 1 8 6 2 4 9 11 12
輸出範例3
55440
評分說明
此題目測資分成四組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組（10 分）：除了編號最大的三個隊員以外其他隊員的編號就是領取房卡的順序，也就是對於所有的1 ≤ i ≤ N−3，Pi = i，如輸入範例1。
第二組（25分）：N ≤ 8。
第三組（50分）：每位隊員若不是第一個領取房卡的，就會在比他編號小1的隊員之後領取房卡（而編號1號隊員會在第N號隊員之後領取），也就是對於所有的2 ≤ i ≤ N，Pi = (Pi−1 mod N)+1，如輸入範例2。
第四組（15分）：無特別限 |
