MYSTERY - Số huyền bí
Tác giả: flashmt
Ngôn ngữ: Pascal
const k=20122007;
var a:array[0..32] of int64;
d:array[0..32] of byte;
uoc:array[1..10000] of int64;
n,num:int64;
re:int64;
procedure rf;
begin
read(n);
end;
procedure init;
var i:byte; j:longint;
begin
a[0]:=1; a[1]:=3;
for i:=2 to 32 do
a[i]:=(a[i-1]*a[i-1]) mod k;
num:=0;
for j:=1 to trunc(sqrt(n)) do
if n mod j = 0 then
begin
num:=num+2;
uoc[num-1]:=j;
uoc[num]:=n div j;
end;
if sqr(trunc(sqrt(n)))=n then dec(num);
end;
function calc(m:int64):int64;
var i:byte; res:int64;
begin
fillchar(d,sizeof(d),0);
i:=1;
while m>0 do
begin
d[i]:=m mod 2;
m:=m div 2;
inc(i);
end;
res:=1;
for i:=0 to 32 do
if d[i]=1 then res:=(res*a[i]) mod k;
calc:=res-1;
end;
procedure pr;
var i:longint;
begin
init;
re:=1;
for i:=1 to num do
re:=(re*calc(uoc[i])) mod k;
end;
procedure wf;
begin
write(re mod k);
end;
begin
rf;
pr;
wf;
end.