#include <cstdio>
#include <cassert>
#include <iostream>
using i64 = long long;
using u64 = unsigned long long;
using u128 = __uint128_t;
struct Mod64 {
Mod64() : n_(0) {}
Mod64(u64 n) : n_(init(n)) {}
static u64 modulus() { return mod; }
static u64 init(u64 w) { return reduce(u128(w) * r2); }
static void set_mod(u64 m) {
mod = m; assert(mod & 1);
inv = m; for (int i = 0; i < 5; ++i) inv *= 2 - inv * m;
r2 = -u128(m) % m;
}
static u64 reduce(u128 x) {
u64 y = u64(x >> 64) - u64((u128(u64(x) * inv) * mod) >> 64);
return i64(y) < 0 ? y + mod : y;
}
Mod64& operator += (Mod64 rhs) { n_ += rhs.n_ - mod; if (i64(n_) < 0) n_ += mod; return *this; }
Mod64 operator + (Mod64 rhs) const { return Mod64(*this) += rhs; }
Mod64& operator *= (Mod64 rhs) { n_ = reduce(u128(n_) * rhs.n_); return *this; }
Mod64 operator * (Mod64 rhs) const { return Mod64(*this) *= rhs; }
u64 get() const { return reduce(n_); }
static u64 mod, inv, r2;
u64 n_;
};
u64 Mod64::mod, Mod64::inv, Mod64::r2;
inline u64 mod128_64_small(u128 a, u64 b) {
u64 q, r;
__asm__ (
"divq\t%4"
: "=a"(q), "=d"(r)
: "0"(u64(a)), "1"(u64(a >> 64)), "rm"(b)
);
return r;
}
u64 fact_mod_fast(int N, u64 mod) {
Mod64::set_mod(mod);
Mod64 ret = Mod64(1), one = ret, t = one;
for (int i = 1; i <= N; ++i) {
ret *= t;
t += one;
}
return ret.get();
}
u64 fact_mod_slow(int N, u64 mod) {
u64 ret = 1;
for (int i = 1; i <= N; ++i) ret = mod128_64_small(u128(ret) * i, mod);
return ret;
}
int main() {
int N; u64 M; scanf("%d %llu", &N, &M);
clock_t t0 = clock();
u64 ans1 = fact_mod_slow(N, M);
clock_t t1 = clock();
u64 ans2 = fact_mod_fast(N, M);
clock_t t2 = clock();
printf("%llu %.3f sec\n", ans1, double(t1 - t0) / CLOCKS_PER_SEC);
printf("%llu %.3f sec\n", ans2, double(t2 - t1) / CLOCKS_PER_SEC);
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNhc3NlcnQ+CgojaW5jbHVkZSA8aW9zdHJlYW0+Cgp1c2luZyBpNjQgPSBsb25nIGxvbmc7CnVzaW5nIHU2NCA9IHVuc2lnbmVkIGxvbmcgbG9uZzsKdXNpbmcgdTEyOCA9IF9fdWludDEyOF90OwoKc3RydWN0IE1vZDY0IHsKICBNb2Q2NCgpIDogbl8oMCkge30KICBNb2Q2NCh1NjQgbikgOiBuXyhpbml0KG4pKSB7fQogIHN0YXRpYyB1NjQgbW9kdWx1cygpIHsgcmV0dXJuIG1vZDsgfQogIHN0YXRpYyB1NjQgaW5pdCh1NjQgdykgeyByZXR1cm4gcmVkdWNlKHUxMjgodykgKiByMik7IH0KICBzdGF0aWMgdm9pZCBzZXRfbW9kKHU2NCBtKSB7CiAgICBtb2QgPSBtOyBhc3NlcnQobW9kICYgMSk7CiAgICBpbnYgPSBtOyBmb3IgKGludCBpID0gMDsgaSA8IDU7ICsraSkgaW52ICo9IDIgLSBpbnYgKiBtOwogICAgcjIgPSAtdTEyOChtKSAlIG07CiAgfQogIHN0YXRpYyB1NjQgcmVkdWNlKHUxMjggeCkgewogICAgdTY0IHkgPSB1NjQoeCA+PiA2NCkgLSB1NjQoKHUxMjgodTY0KHgpICogaW52KSAqIG1vZCkgPj4gNjQpOwogICAgcmV0dXJuIGk2NCh5KSA8IDAgPyB5ICsgbW9kIDogeTsKICB9CiAgTW9kNjQmIG9wZXJhdG9yICs9IChNb2Q2NCByaHMpIHsgbl8gKz0gcmhzLm5fIC0gbW9kOyBpZiAoaTY0KG5fKSA8IDApIG5fICs9IG1vZDsgcmV0dXJuICp0aGlzOyB9CiAgTW9kNjQgb3BlcmF0b3IgKyAoTW9kNjQgcmhzKSBjb25zdCB7IHJldHVybiBNb2Q2NCgqdGhpcykgKz0gcmhzOyB9CiAgTW9kNjQmIG9wZXJhdG9yICo9IChNb2Q2NCByaHMpIHsgbl8gPSByZWR1Y2UodTEyOChuXykgKiByaHMubl8pOyByZXR1cm4gKnRoaXM7IH0KICBNb2Q2NCBvcGVyYXRvciAqIChNb2Q2NCByaHMpIGNvbnN0IHsgcmV0dXJuIE1vZDY0KCp0aGlzKSAqPSByaHM7IH0KICB1NjQgZ2V0KCkgY29uc3QgeyByZXR1cm4gcmVkdWNlKG5fKTsgfQogIHN0YXRpYyB1NjQgbW9kLCBpbnYsIHIyOwogIHU2NCBuXzsKfTsKdTY0IE1vZDY0Ojptb2QsIE1vZDY0OjppbnYsIE1vZDY0OjpyMjsKCmlubGluZSB1NjQgbW9kMTI4XzY0X3NtYWxsKHUxMjggYSwgdTY0IGIpIHsKICB1NjQgcSwgcjsKICBfX2FzbV9fICgKICAgICJkaXZxXHQlNCIKICAgIDogIj1hIihxKSwgIj1kIihyKQogICAgOiAiMCIodTY0KGEpKSwgIjEiKHU2NChhID4+IDY0KSksICJybSIoYikKICApOwogIHJldHVybiByOwp9Cgp1NjQgZmFjdF9tb2RfZmFzdChpbnQgTiwgdTY0IG1vZCkgewogIE1vZDY0OjpzZXRfbW9kKG1vZCk7CiAgTW9kNjQgcmV0ID0gTW9kNjQoMSksIG9uZSA9IHJldCwgdCA9IG9uZTsKICBmb3IgKGludCBpID0gMTsgaSA8PSBOOyArK2kpIHsKICAgIHJldCAqPSB0OwogICAgdCArPSBvbmU7CiAgfQogIHJldHVybiByZXQuZ2V0KCk7Cn0KCnU2NCBmYWN0X21vZF9zbG93KGludCBOLCB1NjQgbW9kKSB7CiAgdTY0IHJldCA9IDE7CiAgZm9yIChpbnQgaSA9IDE7IGkgPD0gTjsgKytpKSByZXQgPSBtb2QxMjhfNjRfc21hbGwodTEyOChyZXQpICogaSwgbW9kKTsKICByZXR1cm4gcmV0Owp9CgppbnQgbWFpbigpIHsKICBpbnQgTjsgdTY0IE07IHNjYW5mKCIlZCAlbGx1IiwgJk4sICZNKTsKICBjbG9ja190IHQwID0gY2xvY2soKTsKICB1NjQgYW5zMSA9IGZhY3RfbW9kX3Nsb3coTiwgTSk7CiAgY2xvY2tfdCB0MSA9IGNsb2NrKCk7CiAgdTY0IGFuczIgPSBmYWN0X21vZF9mYXN0KE4sIE0pOwogIGNsb2NrX3QgdDIgPSBjbG9jaygpOwogIHByaW50ZigiJWxsdSAlLjNmIHNlY1xuIiwgYW5zMSwgZG91YmxlKHQxIC0gdDApIC8gQ0xPQ0tTX1BFUl9TRUMpOwogIHByaW50ZigiJWxsdSAlLjNmIHNlY1xuIiwgYW5zMiwgZG91YmxlKHQyIC0gdDEpIC8gQ0xPQ0tTX1BFUl9TRUMpOwogIHJldHVybiAwOwp9Cg==