题目链接：

题目：

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

 

Input

输入一个数N(0 <= N <= 10^9)

Output

输出：计算结果

Input示例

3

Output示例

40

分析：快速幂+乘法逆元，题目很简洁，其实就是求等比数列的前n项和，等比数列的钱n项和公式为：Sn=a1(1-q^n)/(1-q)，a1=3^0=1,q=3,化简后求解，注意从0到n一共是n+1项哦！！！

乘法逆元：除以一个数取模等于乘以它的乘法逆元，由费马小定理得x=a^(p-2)%p；

乘法逆元学习链接：

AC代码：

#include
     
      #include
      
       #include
       
        #include
        
         #define MOD 1000000007using namespace std;typedef long long ll;ll ksm(ll x,ll n){    ll ans=1;    while (n)    {        if (n&1)           ans=(ans*x)%MOD;        x=(x*x)%MOD;        n>>=1;    }    return ans;}int main(){    ll n,sum;    cin>>n;    sum=(ksm(3,n+1)-1)*ksm(2,MOD-2)%MOD;    cout << sum << endl;    return 0;}