主題
題目連結：
題目意譯：
一個數字字串為「好的」如果其位於偶數位置（索引值從 0 開始）之位數皆為偶數而位於奇數位置之位數為質數（2 、 3 、 5 或是 7）。
例如，"2582" 是好的因為位於偶數位置之位數（2 和 8）皆為偶數且位於奇數位置之位數（5 和 2）為質數。不過，"3245" 則不是好的，因為 3 在偶數位置但它不是偶數。
給定一整數 n，回傳長度 n 的好字串之數量。由於答案可能很大，將其模 10 ^ 9 + 7 後回傳。
一個數字字串為一由數字 0 到 9 組成的字串且可能含有前導零。
限制：
1 ≦ n ≦ 10 ^ 15
範例測資：
範例 1：
輸入： n = 1
輸出： 5
解釋： 長度 1 的好數字為 "0" 、 "2" 、 "4" 、 "6" 、 "8"。
範例 2：
輸入： n = 4
輸出： 400
範例 3：
輸入： n = 50
輸出： 564908303
解題思維：
一個長度為 n 的數字，其奇數位置有 floor(n ÷ 2) 個、偶數有 ceil(n ÷ 2) 個。其中 ceil 為上高斯函數（對於非負數等價於無條件進位到整數位）而 floor 為下高斯函數（對於非負數等價於無條件捨去小數點）。
而因為奇數位置的數字需要是質數，所以每個奇數位置會有 4 種選擇（2 、 3 、 5 、 7）；偶數位置則需要是偶數，所以每個偶數位置會有 5 個選擇（0 、 2 、 4 、 6 、 8）。因此長度為 n 的好數字會有
4 ^ floor(n ÷ 2) × 5 ^ ceil(n ÷ 2)
這麼多個。
而因為我們需要快速得到一個形如 a ^ b 模 10 ^ 9 + 7 的值（直接求 a ^ b 再模 10 ^ 9 + 7 會太耗時），因此我們可以利用快速冪（如這題所述）來求得。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
