Program BinaryAndDecimal;
Const Base = 29876543;

Var f: Text;
    a, b: Array [-8..0] of LongInt;
    n, m: Int64;
    i, j: LongInt;
Begin
//  Assign(f, 'nobinary.in'); Reset(f);
  Readln(n);
//  Close(f);

  For i:= -8 To -1 Do Begin
    b[i]:= 0;
  End;
  b[0]:= 1;

  While n>0 Do Begin
    For i:= -8 To 0 Do Begin
      a[i]:= b[i];
      b[i]:= 0;
    End;
    m:= n div 2;
    For i:= -8 To 0 Do Begin
      If (n+i>=0) Then Begin
        For j:= (n+i) div 2 - m DownTo (n+i) div 2 - m - 4 Do Begin
          b[j]:= (b[j]+a[i]) mod base;
        End;
      End;
    End;
    n:= m;
  End;

//  Assign(f, 'nobinary.out'); Rewrite(f);
  Writeln(b[0]);
//  Close(f);
End.
