题解 | 牛妹的位运算

// 属于是猜对的
/*
	用快速幂计算4的整数次幂然后累加到一起
	具体证明方法采用数学归纳法？？？
	用等比求和不行，因为取模意义下不能进行除法运算
*/
#include <stdio.h>
#define ll long long 
#define MOD 1000000007
ll rd()
{
    ll rs = 0,c = getchar();
    while (c  < '0'||c > '9') c = getchar();
    while (c >='0'&&c <= '9')
    {
        rs = (rs<<3)+(rs<<1)+c-'0';
        c = getchar();
    }return rs;
}
void wt(ll t)
{
    if (t > 9)wt(t/10);
    putchar(t%10|48);
}
ll qp(ll k)
{
    ll rs = 1,b = 4;
    while (k)
    {
        if (k&1)
            rs = (rs*b)%MOD;
        b = (b*b)%MOD;
        k>>=1;
    }return rs;
}
void solve()
{
    ll k = rd(),rs = 0;
    for (ll i = 0;i < k;i++)
    {rs= (rs+qp(i))%MOD;}
    wt(rs);
}

int main() {
    solve();    
    return 0;
}