题目描述

小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;
}
01-02 07:07