51nod - 1013 3的幂的和

求：3^0 + 3^1 +...+ 3^(N) mod 1000000007

Input

輸入一個數N(0 <= N <= 10^9)
           

Output

輸出：計算結果
           

Input示例

3
           

Output示例

40
           

思路：

根據等比數列和的公式，本題的解為((3^(n+1) - 1) / 2) % 1000000007。

如果x與y的積除以z所得的餘數為1，即xy = 1 (mod z)，則稱x和y對于模數z來說互為逆元。假定(B∗X)%C=1則

A/B%C=A/B∗1%C=A/B%C∗1%C=A/B%C∗(B∗X)%C=(A/B∗B∗X)%C=(A∗X)%C

在本題中，2*500000004 = 1 （mod 1000000007），是以500000004是2對于1000000007的逆元。則

(3^(n+1)−1)/2%1000000007=(3^(n+1)−1)∗500000004%1000000007

這樣，就将除法運算轉換為乘法運算。

#include <iostream>
#include <cstring>
using namespace std;

typedef long long int ll;

ll MOD = 1e9 + 7;
ll mod_pow(ll a, ll k)
{
	ll base = a;
	ll result = 1;
	while (k > 0)
	{
		if (k & 1)
		{
			result = (result * base) % MOD;
		}

		k /= 2;
		base = (base * base) % MOD;
	}

	return result;
}

int main()
{
	ll n;
	cin >> n;
	ll result = ((mod_pow(3, n+1) - 1) * 500000004) % MOD;
	cout << result << endl;

	return 0;
}