题目描述

小Biu所在的部落是一个魔法部落，部落中一共有n+1个人，小Biu是魔法部落中最菜的，所以他的魔力值为1，魔法部落中n个人的魔法值都不相同，第一个人的魔法值是小Biu的3倍，第二个人的魔法值是第一个人的3倍，以此类推。
现在小Biu想知道整个部落的魔法值和是多少？由于答案比较大，请把答案对1e9+7取模之后输出。

输入

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

输出

输出：整个部落的魔法值和模1e9+7。

样例输入

3
样例输出

40
提示

3^0+3^1+3^2+3^3 = 1+3+9+27 = 40

对于20%的数据，n<=100；
对于40%的数据，n<=1000000；
对于100%的数据,n<=1000000000；

 

 

 

 

#include<bits/stdc++.h>
using namespace std;
const int N = 1e9+7;
typedef long long ll;
ll k(ll a,ll b,ll y){  //快速幂取模
    ll t = 1;
    while(b) {
        if(b%2 != 0) {
            t = (a*t)%y;
            b--;
        }
        a = (a*a)%y;
        b /= 2;
    }
    return t;
}

int main()
{
    ll n;
    cin>>n;
    ll x = k(3,n+1,N);
    if((x-1)%2 != 0) {  //判断奇偶
        x = x + N;  //如果是奇数就加上1e9+7让它变成偶数
    }
    x = (x-1)/2;
    cout<<x<<endl;
}