主題
題目連結：
題目意譯：
現在有一個有著 n 的頂點的正凸多邊形。這些頂點將以順時針方向編號為 0 到 n - 1，而每一個頂點有著恰好一隻猴子在。下圖代表著一個有著 6 個頂點的凸多邊形。
每一隻猴子將同時移動到相鄰的頂點。一個頂點 i 的相鄰頂點為：
順時針方向的頂點 (i + 1) % n，或
逆時針方向的頂點 (i - 1 + n) % n。
如果至少兩隻猴子在移動後處於同一個頂點上或是在某一條邊上相會，則此為一次「碰撞」。
回傳至少有一次碰撞的猴子移動方法數。由於答案可能很大，將其模 10 ^ 9 + 7 後再回傳。
注意到每一隻猴子只能移動一次。
限制：
3 ≦ n ≦ 10 ^ 9
範例測資：
範例 1：
輸入： n = 3
輸出： 6
解釋： 有 8 種可能的移動方式。
其中兩個讓它們在同一點碰撞的方式為：
- 1 號猴子往順時針方向移動；2 號猴子往逆時針方向移動；3 號猴子往順時針方向移動。1 號猴子和 2 號猴子發生碰撞。
- 1 號猴子往逆時針方向移動；2 號猴子往逆時針方向移動；3 號猴子往順時針方向移動。1 號猴子和 3 號猴子發生碰撞。
可以證明有 6 個方式來使猴子們之間有碰撞發生。
範例 2：
輸入： n = 4
輸出： 14
解釋： 可以證明有 14 個方式來使猴子們之間有碰撞發生。
解題思維：
可以看到實際上只要 n > 1，唯二不會有任何碰撞發生的方式為所有猴子同時往順時針方向移動或是同時往逆時針方向移動。
因此會有至少一次碰撞發生的方法數為
2 ^ n - 2
種。而這個數字可以利用快速冪來算出，參見這個遠古時代的解題心得（該方式可以順便求上式模 10 ^ 9 + 7 之值，因為乘法和模運算滿足「先乘後模」與「先模後乘」是同餘的，即等價）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
