a108. TOI 2024/11 潛力組：入住旅館

題目描述

N 位隊員的編號是 1 到 N，彼此不同。他們按照隊伍順序領取房卡。每位隊員先嘗試 1 號房；若目前嘗試的 x 號房已有人，則比較兩人的隊員編號：

• 自己的編號較小，接著嘗試 2x 號房。
• 自己的編號較大，接著嘗試 2x+1 號房。 重複上述步驟，直到拿到尚未被領取的房卡。

已知第一次領房卡的隊伍順序。請計算全部可能的隊伍排列中，有多少種排列會讓每位隊員都取得與第一次相同的房間號碼。

輸入格式

第一行輸入 N，3 ≤ N ≤ 1000。 第二行有 N 個相異整數 P1 到 PN，是 1 到 N 的排列，表示第一次領房卡的先後順序。

輸出格式

輸出符合條件的排列數除以 1000000007 的餘數。

來源

TOI 2024 年 11 月潛力組〈入住旅館〉。依官方題意重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202411/CheckIn.pdf