MYSTERY PASCAL

const hs=20122007;
var l,r,x,y,s:qword;
    n,i,j:longint;

function lt(a,b:int64):int64;
var t,s:int64;
begin
    iF b=0 then exit(1);
    t:=lt(a,b div 2);
    s:=(t*t) mod hs;
    iF b mod 2=0 then exit(s)
    else exit((s*(a mod hs)) mod hs);
end;

procedure giai;
begin
    s:=1;
    for i:=1 to trunc(sqrt(n)) do
        IF n mod i=0 then
        begin
            s:=(s*(lt(3,i)-1)) mod hs;
            IF i<>(n div i) then s:=(s*(lt(3, n div i)-1)) mod hs;
        end;
    write(s);
end;

begin
    assign(input,'MYSTERY.inp');reset(input);
    assign(output,'MYSTERY.out');rewrite(output);
    readln(n);
    giai;
end.