// Arhiva de probleme - 12-Perm

var
    n, i, j, k : longint;
    ti, ti1, ti2, ti3 :longint;
    f :text;

begin
assign  (f, '12perm.in');
reset   (f);
readln  (f,n);
close   (f);

assign  (f, '12perm.out');
rewrite  (f);
//pt i = 4
ti1 := 12; ti2 := 6; ti3 :=2;

if n=1 then ti := ti3;
if n=2 then ti := ti2;
if n=3 then ti := ti1;
if n=4 then ti := 12;

for i:=5 to n do
    begin
    ti := (ti1 + ti3 + 2*(i-2)) mod 104876;
    ti3 := ti2; ti2 := ti1; ti1 := ti;
    end;

writeln (f, ti);
close   (f);
end.