題目連結：
題目大意：
輸入有多列，每列給定兩正整數 x 、 n（1 ≦ x ≦ 10 ^ 6，1 ≦ n < 2 ^ 63。當 x = n = 0 時，代表輸入結束），試問 1 + x + x ^ 2 + x ^ 3 + …… + x ^ n 之值為何？由於答案可能很大，所以請將答案模 10 ^ 9 + 7 後輸出。
範例輸入：
2 1
3 2
4 4
1 100
5 1000
1000000 2147483648
0 0
範例輸出：
3
13
341
101
211933906
67476844
解題思維：
題目的 1 + x + x ^ 2 + x ^ 3 + …… + x ^ n 即是一個等比級數，可以看到其等價於
(x ^ (n + 1) - 1) ÷ (x - 1)
x ^ (n + 1) 可以利用快速冪求出（參見這題）。
現在我們需要求 (x ^ (n + 1) - 1) 除以 (x - 1) 的同餘結果，而除法在餘數系統下是以乘法定義（即模反元素，參見這題的說明）。因此我們需要求 (x - 1) 在模 10 ^ 9 + 7 下的模反元素。
而根據費馬小定理（Fermat's Little Theorem）—— a ^ (p - 1) ≡ 1 (mod p)，其中 a 為任意整數、p 為一質數。再加上 10 ^ 9 + 7 是一個質數，因此可以看到
(x - 1) × (x - 1) ^ (10 ^ 9 + 5) ≡ 1 (mod 10 ^ 9 + 7)
其中 (x - 1) ^ (10 ^ 9 + 5) 恰好為模反元素（符合定義），因此我們可以再利用一個快速冪求得該值。
最後將 (x ^ (n + 1) - 1) × (x - 1) ^ (10 ^ 9 + 5) 取餘數即是所求。
但是上述公式會在 x = 1 時出現除以 0 之情形，所以公式將不再管用。不過此時可以看到其所求值恰好為 1 + 1 + 1 ^ 2 + …… 1 ^ n = n + 1。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
