rogvaiv

#include <fstream>
#include <cstring>
#define MOD 1000000007
#define Nmax 1000001
using namespace std;
ifstream f("rogvaiv.in");
ofstream g("rogvaiv.out");

typedef int NrMare[Nmax];
NrMare n;

long long Divide(NrMare x,long long n)
///x = x /n, returneaza x%n
{
  long long i,r=0;
  for(i=x[0];i>0;i--)
  {
    r=10*r+x[i];
    x[i]=r/n;
    r%=n;
  }
  for(;x[x[0]]==0 && x[0]>1;)
    x[0]--;
  return r;
}

/// Ridicam la putere in timp logaritmic, folosind:
///    7^n = 7^(n/2) * 7^(n/2), n%2==0   OR   2^(n-1)*2, n%2==1

long long PutereLog(int baza,long long n)
{
    ///Calculam puterea cu modulo
    if(n==0)
        return 1;

    if(n%2==0)
    {
        long long rezultat=PutereLog(baza,n/2);
        return (rezultat*rezultat)%MOD;
    }
    else
    {
        return (PutereLog(baza,n-1)*baza)%MOD;
    }
}

int main()
{
    char s[Nmax];
    f.getline(s,Nmax); /// Il citim pe n ca sir de caractere
    int nc=strlen(s); /// Numarul de cifre ale lui n
    for(int i=1;i<=nc;++i) /// Punem cifrele din s in n in ordine inersa (lucram cu numere mari)
        n[i]=s[nc-i]-'0';
    n[0]=nc;
    long long rest=Divide(n,1000000006);
    g<<PutereLog(7,rest);
    return 0;
}