Cerința

Se dă un număr natural N. Să se calculeze expresia:

$E = (2^0 +2^1 + 2^2 + 2^3 + … + 2^N ) \% 1 000 000 007$

unde x % y reprezintă restul împărţirii lui x la y.

Date de intrare

Fișierul de intrare sume1.in conține pe prima linie numărul N.

Date de ieșire

Fișierul de ieșire sume1.out va conține pe prima linie rezultatul expresiei E.

Restricții și precizări

• 1 ≤ N ≤ 1017
• 1000000007 este număr prim.
• Pentru 30% din teste, N ≤ 106

Exemplul 1

sume1.in

4

sume1.out

31

Exemplul 2

sume1.in

9

sume1.out

1023

#include <bits/stdc++.h>
using namespace std;

ifstream cin("sume1.in");
ofstream cout("sume1.out");

long long int putere(int x , long long int n , int mod)
{
    long long int val;
    if(n == 1)
        return x;
    else
    {
        val = putere(x , n/2 , mod);
        if(n % 2 == 0)
            return val * val % mod;
        else
            return val * val % mod * 2 % mod;
    }
}

int main()
{
    long long int n;
    cin >> n;
    cout << putere(2 , n + 1 , 1000000007) - 1;
    return 0;
}