//na                            :cuixiaofei;
//da                            :08_09_19;
program puzhuan;
  var
    n                           :longint;
    a                           :array[0..100000] of longint;
    f1,f2                       :text;
  procedure init;
  begin
    assign(f1,'puzhuan.in');
    reset(f1);
    assign(f2,'puzhuan.out');
    rewrite(f2);
    readln(f1,n);
    fillchar(a,sizeof(a),0);
    a[0]:=1;
    a[1]:=1;
    a[2]:=2;
  end;
  procedure main;
    var
      i                         :longint;
  begin
    for i:=2 to n do
      a[i]:=(a[i-2]*2+a[i-1]) mod 12345;
  end;
  procedure print;
  begin
    writeln(f2,a[n]);
    close(f1);
    close(f2);
  end;
  begin
    init;
    main;
    print;
  end.