Question

#1428 Sume1

Această problemă a fost preluată dintr-un concurs. Rezultatele evaluării pot fi diferite față ale evaluării în concurs.
Enunț
Soluții


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

E=(20+21+22+23+…+2N)%1000000007
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

Answer 1

#include <iostream>

#include <fstream>

using namespace std;

ifstream in("sume1.in");

ofstream out("sume1.out");

long long putere(long long n)

{

   if(n==1)

       return 2%1000000007;

   if(n%2==0)

       return (putere(n/2)*putere(n/2))%1000000007;

   if(n%2==1)

       return (putere(n-1)*2)%1000000007;

}

int main()

{

   long long N,i=0,s=0;

   in>>N;

   s=putere(N+1)-1;

   out<<s%1000000007;

}