Polynomial calculation of N! modulo M

Revision ru1, by blyat, 2019-08-03 19:35:36

Hello, Codeforces! Today I've faced the following problem: is it possible to calculate N! modulo M (M is prime) in polynomial (relative to length of M) time? I thought it would be pretty popular problem, but I couldn't google anything useful. Does anybody know such algorithm or proofs that such algorithm does not exist?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English blyat 2019-08-03 19:36:56 348 Initial revision for English translation
ru2 Russian blyat 2019-08-03 19:36:07 12 Мелкая правка: 'oofs that such algorithm does not ' -> 'oofs that it does not '
ru1 Russian blyat 2019-08-03 19:35:36 360 Первая редакция (опубликовано)