回帖：重做了一遍
增加了1000003的倍数的处理
减少了小于7时的判断（本来以为小于7时不能用费马小定理）
var
n,r,t:int64;
procedure power(a,b:int64;var t:int64);
var
i:longint;
begin
for i:=1 to a do
t:=t*n mod b;
end;
begin
read(n);
if n mod 1000003=0
then write(0)
else
if n=2
then write(16)
else
begin
r:=1;
power(n,1000002,r);
t:=1;
power(r,1000003,t);
write(t);
end;
end.