var n,ans,m:longint;
function pow(x,n:longint):longint;
begin
 if n=0 then exit(1);
 pow:=pow(x, n div 2) MOD m;
 pow:=pow*pow MOD M;
 if n mod 2=1 then pow:=pow*x MOD M;
end;
begin
//assign(input,'H1N1.IN');
//assign(output,'H1N1.OUT');
//reset(input);
//rewrite(output);
 m:=7222222;
 readln(n);
 ans:=pow(2,n-1)mod M;
 writeln((ans+ans*ans) mod m);
close(input);
close(output);
end.