program main
  integer*8::N
  integer*8::modulo=3000000021_8
  read *,N
  print '(i0)',MOD(MOD(N,modulo)*MOD(N,modulo)*MOD(N,modulo),modulo)
end program main