結果
問題 | No.502 階乗を計算するだけ |
ユーザー |
|
提出日時 | 2019-07-25 16:55:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 1,000 ms |
コード長 | 32,802 bytes |
コンパイル時間 | 1,650 ms |
コンパイル使用メモリ | 196,464 KB |
最終ジャッジ日時 | 2025-01-07 07:29:37 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 52 |
ソースコード
/****/// header {{{#include <bits/stdc++.h>using namespace std;#define CPP_STR(x) CPP_STR_I(x)#define CPP_CAT(x,y) CPP_CAT_I(x,y)#define CPP_STR_I(args...) #args#define CPP_CAT_I(x,y) x ## y#define SFINAE(pred...) std::enable_if_t<(pred), std::nullptr_t> = nullptr#define ASSERT(expr...) assert((expr))using i8 = int8_t;using u8 = uint8_t;using i16 = int16_t;using u16 = uint16_t;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;using f32 = float;using f64 = double;using f80 = __float80;// }}}constexpr i64 INF = INT64_C(1'010'000'000'000'000'017);constexpr f64 FINF = 1e100;constexpr i64 MOD = INT64_C(1'000'000'007);constexpr f64 EPS = 1e-12;constexpr f64 PI = 3.14159265358979323846;// util {{{#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)#define REP(i, n) FOR(i, 0, n)#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))#define LIFT(f) ([](auto&&... args) -> decltype(auto) { return (f)(std::forward<decltype(args)>(args)...); })template<typename C>constexpr i64 SIZE(const C& c) noexcept { return static_cast<i64>(c.size()); }template<typename T, size_t N>constexpr i64 SIZE(const T (&)[N]) noexcept { return static_cast<i64>(N); }template<typename T, typename U, typename Comp=less<>>constexpr bool chmax(T& xmax, const U& x, Comp comp={}) noexcept {if(comp(xmax, x)) {xmax = x;return true;}return false;}template<typename T, typename U, typename Comp=less<>>constexpr bool chmin(T& xmin, const U& x, Comp comp={}) noexcept {if(comp(x, xmin)) {xmin = x;return true;}return false;}template<typename BinaryFunc, typename UnaryFunc>auto ON(BinaryFunc&& bf, UnaryFunc&& uf) {return [bf=forward<BinaryFunc>(bf),uf=forward<UnaryFunc>(uf)](const auto& x, const auto& y) {return bf(uf(x), uf(y));};}template<typename F>auto LT_ON(F&& f) {return ON(less<>{}, forward<F>(f));}template<typename F>auto GT_ON(F&& f) {return ON(greater<>{}, forward<F>(f));}template<typename F>auto EQ_ON(F&& f) {return ON(equal_to<>{}, forward<F>(f));}template<typename F>auto NE_ON(F&& f) {return ON(not_equal_to<>{}, forward<F>(f));}// tuple {{{template<i64 I=0, typename F, typename... TS, SFINAE(sizeof...(TS) == I)>void tuple_enumerate(tuple<TS...>&, F&&) {}template<i64 I=0, typename F, typename... TS, SFINAE(sizeof...(TS) > I)>void tuple_enumerate(tuple<TS...>& t, F&& f) {f(I, get<I>(t));tuple_enumerate<I+1>(t, forward<F>(f));}template<i64 I=0, typename F, typename... TS, SFINAE(sizeof...(TS) == I)>void tuple_enumerate(const tuple<TS...>&, F&&) {}template<i64 I=0, typename F, typename... TS, SFINAE(sizeof...(TS) > I)>void tuple_enumerate(const tuple<TS...>& t, F&& f) {f(I, get<I>(t));tuple_enumerate<I+1>(t, forward<F>(f));}// }}}// container {{{template<typename T> struct is_container : false_type {};template<typename T, size_t N> struct is_container<array<T,N>> : true_type {};template<typename... Args> struct is_container<vector<Args...>> : true_type {};template<typename... Args> struct is_container<deque<Args...>> : true_type {};template<typename... Args> struct is_container<list<Args...>> : true_type {};template<typename... Args> struct is_container<forward_list<Args...>> : true_type {};template<typename... Args> struct is_container<set<Args...>> : true_type {};template<typename... Args> struct is_container<multiset<Args...>> : true_type {};template<typename... Args> struct is_container<unordered_set<Args...>> : true_type {};template<typename... Args> struct is_container<unordered_multiset<Args...>> : true_type {};template<typename... Args> struct is_container<map<Args...>> : true_type {};template<typename... Args> struct is_container<multimap<Args...>> : true_type {};template<typename... Args> struct is_container<unordered_map<Args...>> : true_type {};template<typename... Args> struct is_container<unordered_multimap<Args...>> : true_type {};template<typename T, typename Enable=void>struct ProconHash {size_t operator()(const T& x) const noexcept {return hash<T>{}(x);}};template<typename T>size_t procon_hash_value(const T& x) noexcept {return ProconHash<T>{}(x);}size_t procon_hash_combine(size_t h1, size_t h2) noexcept {constexpr size_t M = UINT64_C(0xc6a4a7935bd1e995);constexpr int R = 47;h2 *= M;h2 ^= h2 >> R;h2 *= M;h1 ^= h2;h1 *= M;h1 += 0xe6546b64;return h1;}template<typename T1, typename T2>struct ProconHash<pair<T1,T2>> {size_t operator()(const pair<T1,T2>& p) const noexcept {size_t h1 = procon_hash_value(p.first);size_t h2 = procon_hash_value(p.second);return procon_hash_combine(h1, h2);}};template<typename... TS>struct ProconHash<tuple<TS...>> {size_t operator()(const tuple<TS...>& t) const noexcept {size_t h = 0;tuple_enumerate(t, [&h](const auto& e) {h = procon_hash_combine(h, procon_hash_value(e));});return h;}};template<typename C>struct ProconHash<C,enable_if_t<is_container<C>::value>> {size_t operator()(const C& c) const noexcept {size_t h = 0;for(const auto& e : c)h = procon_hash_combine(h, procon_hash_value(e));return h;}};template<typename T, typename Hash=ProconHash<T>, typename Eq=equal_to<T>>using HashSet = unordered_set<T,Hash,Eq>;template<typename K, typename V, typename Hash=ProconHash<K>, typename Eq=equal_to<K>>using HashMap = unordered_map<K,V,Hash,Eq>;template<typename T, typename Hash=ProconHash<T>, typename Eq=equal_to<T>>using HashMultiset = unordered_multiset<T,Hash,Eq>;template<typename K, typename V, typename Hash=ProconHash<K>, typename Eq=equal_to<K>>using HashMultimap = unordered_multimap<K,V,Hash,Eq>;template<typename T>auto vec_make(i64 n, T x) {return vector<T>(n, x);}template<typename T, typename... Args, SFINAE(sizeof...(Args) >= 2)>auto vec_make(i64 n, Args... args) {auto inner = vec_make<T>(args...);return vector<decltype(inner)>(n, inner);}template<typename T>auto vec_reserve(i64 cap) {vector<T> res;res.reserve(cap);return res;}template<typename T=i64>auto vec_iota(i64 n, T init={}) {vector<i64> res(n);ALL(iota, res, init);return res;}template<typename T, typename Comp, typename Cont=vector<T>>auto priority_queue_make(const Comp& comp, Cont&& cont={}) {return priority_queue<T,remove_reference_t<Cont>,Comp>(comp, forward<Cont>(cont));}template<typename T, typename Comp>auto priority_queue_reserve(const Comp& comp, i64 cap) {return priority_queue<T,vector<T>,Comp>(comp, vec_reserve<T>(cap));}template<typename T, size_t N, size_t... NS>struct ArrayType {using type = array<typename ArrayType<T,NS...>::type,N>;};template<typename T, size_t N>struct ArrayType<T,N> {using type = array<T,N>;};template<typename T, size_t... NS>using Array = typename ArrayType<T,NS...>::type;template<typename T, size_t N>T& array_at(Array<T,N>& ary, i64 i) {return ary[i];}template<typename T, size_t N, size_t... NS, typename... Args>T& array_at(Array<T,N,NS...>& ary, i64 i, Args... args) {return array_at<T,NS...>(ary[i], args...);}template<typename T, size_t N>const T& array_at(const Array<T,N>& ary, i64 i) {return ary[i];}template<typename T, size_t N, size_t... NS, typename... Args>const T& array_at(const Array<T,N,NS...>& ary, i64 i, Args... args) {return array_at<T,NS...>(ary[i], args...);}template<typename T, typename C>T POP(stack<T,C>& stk) {T x = stk.top(); stk.pop();return x;}template<typename T, typename C>T POP(queue<T,C>& que) {T x = que.front(); que.pop();return x;}template<typename T, typename C, typename Comp>T POP(priority_queue<T,C,Comp>& que) {T x = que.top(); que.pop();return x;}// }}}// fixpoint {{{template<typename F>class FixPoint {public:explicit constexpr FixPoint(F&& f) : f_(forward<F>(f)) {}template<typename... Args>constexpr decltype(auto) operator()(Args&&... args) const {return f_(*this, forward<Args>(args)...);}private:F f_;};template<typename F>constexpr decltype(auto) FIX(F&& f) {return FixPoint<F>(forward<F>(f));}template<typename F, size_t... NS>class FixPointMemo {public:explicit FixPointMemo(F&& f) : f_(forward<F>(f)) {}template<typename... Args>decltype(auto) operator()(Args... args) const {using R = decltype(f_(*this,args...));static Array<bool,NS...> done {};static Array<R,NS...> memo;if(!array_at<bool,NS...>(done,args...)) {array_at<R,NS...>(memo,args...) = f_(*this,args...);array_at<bool,NS...>(done,args...) = true;}return array_at<R,NS...>(memo,args...);}private:F f_;};template<size_t... NS, typename F>decltype(auto) FIXMEMO(F&& f) {return FixPointMemo<F,NS...>(forward<F>(f));}// }}}// string {{{auto str_reserve(i64 cap) {string res;res.reserve(cap);return res;}// }}}// input {{{template<typename T, typename Enable=void>struct Scan {static T scan(istream& in) {T res;in >> res;return res;}};template<typename T, typename Enable=void>struct Scan1;template<typename T>struct Scan1<T,enable_if_t<is_integral<T>::value && !is_same<T,bool>::value>> {static T scan1(istream& in) {return Scan<T>::scan(in) - 1;}};template<typename T1, typename T2>struct Scan<pair<T1,T2>> {static pair<T1,T2> scan(istream& in) {return make_pair(Scan<T1>::scan(in), Scan<T2>::scan(in));}};template<typename T1, typename T2>struct Scan1<pair<T1,T2>> {static pair<T1,T2> scan1(istream& in) {return make_pair(Scan1<T1>::scan1(in), Scan1<T2>::scan1(in));}};template<typename... TS>struct Scan<tuple<TS...>> {static tuple<TS...> scan(istream& in) {return scan_impl<0>(in);}private:template<i64 I, SFINAE(sizeof...(TS) == I)>static auto scan_impl(istream&) {return make_tuple();}template<i64 I, SFINAE(sizeof...(TS) > I)>static auto scan_impl(istream& in) {using T = tuple_element_t<I,tuple<TS...>>;auto head = make_tuple(Scan<T>::scan(in));return tuple_cat(head, scan_impl<I+1>(in));}};template<typename... TS>struct Scan1<tuple<TS...>> {static tuple<TS...> scan1(istream& in) {return scan1_impl<0>(in);}private:template<i64 I, SFINAE(sizeof...(TS) == I)>static auto scan1_impl(istream&) {return make_tuple();}template<i64 I, SFINAE(sizeof...(TS) > I)>static auto scan1_impl(istream& in) {using T = tuple_element_t<I,tuple<TS...>>;auto head = make_tuple(Scan1<T>::scan1(in));return tuple_cat(head, scan1_impl<I+1>(in));}};template<typename T=i64>T RD() {return Scan<T>::scan(cin);}template<typename T=i64>T RD1() {return Scan1<T>::scan1(cin);}template<typename T=i64>auto RD_VEC(i64 n) {auto res = vec_reserve<T>(n);REP(_, n) {res.emplace_back(RD<T>());}return res;}template<typename T=i64>auto RD1_VEC(i64 n) {auto res = vec_reserve<T>(n);REP(_, n) {res.emplace_back(RD1<T>());}return res;}template<typename T=i64>auto RD_VEC2(i64 h, i64 w) {auto res = vec_reserve<vector<T>>(h);REP(_, h) {res.emplace_back(RD_VEC<T>(w));}return res;}template<typename T=i64>auto RD1_VEC2(i64 h, i64 w) {auto res = vec_reserve<vector<T>>(h);REP(_, h) {res.emplace_back(RD1_VEC<T>(w));}return res;}// }}}// output {{{template<typename T, typename Enable=void>struct Fmt {static void fmt(ostream& out, const T& x) { out << x; }};template<typename T>void fmt_write(ostream& out, const T& x) {Fmt<T>::fmt(out, x);}template<typename... TS>struct Fmt<tuple<TS...>> {static void fmt(ostream& out, const tuple<TS...>& t) {tuple_enumerate(t, [&out](i64 i, const auto& e) {if(i != 0) out << ' ';fmt_write(out, e);});}};template<typename T1, typename T2>struct Fmt<pair<T1,T2>> {static void fmt(ostream& out, const pair<T1,T2>& p) {return fmt_write(out, make_tuple(p.first,p.second));}};template<typename C>struct Fmt<C,enable_if_t<is_container<C>::value>> {static void fmt(ostream& out, const C& c) {for(auto it = begin(c); it != end(c); ++it) {if(it != begin(c)) out << ' ';fmt_write(out, *it);}}};void PRINT() {}template<typename T, typename... TS>void PRINT(const T& x, const TS&... args) {fmt_write(cout, x);if(sizeof...(args) > 0) {cout << ' ';PRINT(args...);}}template<typename... TS>void PRINTLN(const TS&... args) {PRINT(args...);cout << '\n';}// }}}// debug {{{template<typename T, typename Enable=void>struct Dbg {static void dbg(ostream& out, const T& x) { out << x; }};template<typename T>void dbg_write(ostream& out, const T& x) {return Dbg<T>::dbg(out, x);}template<>struct Dbg<i64> {static void dbg(ostream& out, i64 x) {if(x == INF)out << "INF";else if(x == -INF)out << "-INF";elseout << x;}};template<>struct Dbg<f64> {static void dbg(ostream& out, f64 x) {#pragma GCC diagnostic push#pragma GCC diagnostic ignored "-Wfloat-equal"if(x == FINF)out << "FINF";else if(x == -FINF)out << "-FINF";elseout << x;#pragma GCC diagnostic pop}};template<typename T, size_t N>struct Dbg<T[N]> {static void dbg(ostream& out, const T (&ary)[N]) {out << "[";REP(i, N) {if(i != 0) out << ",";dbg_write(out, ary[i]);}out << "]";}};template<typename... TS>struct Dbg<tuple<TS...>> {static void dbg(ostream& out, const tuple<TS...>& t) {out << "(";tuple_enumerate(t, [&out](i64 i, const auto& e) {if(i != 0) out << ",";dbg_write(out, e);});out << ")";}};template<typename T1, typename T2>struct Dbg<pair<T1,T2>> {static void dbg(ostream& out, const pair<T1,T2>& p) {return dbg_write(out, make_tuple(p.first,p.second));}};template<typename C>struct Dbg<C,enable_if_t<is_container<C>::value>> {static void dbg(ostream& out, const C& c) {out << "[";for(auto it = begin(c); it != end(c); ++it) {if(it != begin(c)) out << ",";dbg_write(out, *it);}out << "]";}};template<typename T, typename C>struct Dbg<stack<T,C>> {static void dbg(ostream& out, stack<T,C> stk) {out << "[";while(!stk.empty()) {dbg_write(out,stk.top()); stk.pop();if(!stk.empty()) out << ",";}out << "]";}};template<typename T, typename C>struct Dbg<queue<T,C>> {static void dbg(ostream& out, queue<T,C> que) {out << "[";while(!que.empty()) {dbg_write(out,que.front()); que.pop();if(!que.empty()) out << ",";}out << "]";}};template<typename T, typename C, typename Comp>struct Dbg<priority_queue<T,C,Comp>> {static void dbg(ostream& out, priority_queue<T,C,Comp> que) {out << "[";while(!que.empty()) {dbg_write(out,que.top()); que.pop();if(!que.empty()) out << ",";}out << "]";}};template<typename T>void DBG_IMPL(i64 line, const char* expr, const T& value) {cerr << "[L " << line << "]: ";cerr << expr << " = ";dbg_write(cerr, value);cerr << "\n";}void DBG_IMPL_HELPER() {}template<typename T, typename... TS>void DBG_IMPL_HELPER(const T& x, const TS&... args) {dbg_write(cerr, x);if(sizeof...(args) > 0) {cerr << ",";DBG_IMPL_HELPER(args...);}}template<typename... TS>void DBG_IMPL(i64 line, const char* expr, const TS&... value) {cerr << "[L " << line << "]: ";cerr << "(" << expr << ") = (";DBG_IMPL_HELPER(value...);cerr << ")\n";}template<size_t N, typename T, SFINAE(rank<T>::value == 0)>void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array<i64,N>&, const array<i64,N>&) {dbg_write(out, x);}template<size_t N, typename T, SFINAE(rank<T>::value > 0)>void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array<i64,N>& sizes, const array<i64,N>& offs) {i64 k = N - rank<T>::value;i64 off = offs[k];i64 siz = sizes[k];if(siz == 0) siz = extent<T>::value - off;out << "[";FOR(i, off, off+siz) {if(i != off) out << ",";DBG_DP_IMPL_HELPER(out, x[i], sizes, offs);}out << "]";}template<typename T, SFINAE(rank<T>::value > 0)>void DBG_DP_IMPL(i64 line, const char* expr, const T& dp,const array<i64,rank<T>::value>& sizes={},const array<i64,rank<T>::value>& offs={}){cerr << "[L " << line << "]: ";cerr << expr << " = ";DBG_DP_IMPL_HELPER<rank<T>::value>(cerr, dp, sizes, offs);cerr << "\n";}template<typename T>void DBG_GRID_IMPL(i64 line, const char* expr, const vector<T>& grid) {cerr << "[L " << line << "]: ";cerr << expr << ":\n";for(const auto& row : grid) {dbg_write(cerr, row);cerr << "\n";}cerr << "\n";}#ifdef PROCON_LOCAL#define DBG(args...) DBG_IMPL(__LINE__, CPP_STR_I(args), args)#define DBG_DP(args...) DBG_DP_IMPL(__LINE__, CPP_STR_I(args), args)#define DBG_GRID(args...) DBG_GRID_IMPL(__LINE__, CPP_STR_I(args), args)#else#define DBG(args...)#define DBG_DP(args...)#define DBG_GRID(args...)#endif// }}}// modint {{{template<i64 M>struct ModIntT {static_assert(M >= 2, "");i64 v_; // [0,M)ModIntT() : v_(0) {}ModIntT(i64 v) {i64 r = v % M;v_ = r >= 0 ? r : r+M;}ModIntT operator-() const {return ModIntT(-v_);}ModIntT& operator+=(ModIntT rhs) {v_ += rhs.v_;v_ %= M;return *this;}ModIntT& operator-=(ModIntT rhs) {v_ += M;v_ -= rhs.v_;v_ %= M;return *this;}ModIntT& operator*=(ModIntT rhs) {v_ *= rhs.v_;v_ %= M;return *this;}ModIntT& operator++() {return *this += 1;}ModIntT& operator--() {return *this -= 1;}ModIntT operator++(int) {return exchange(*this, *this+1);}ModIntT operator--(int) {return exchange(*this, *this-1);}explicit operator i64() const { return v_; }};template<i64 M>ModIntT<M> operator+(ModIntT<M> lhs, ModIntT<M> rhs) { return ModIntT<M>(lhs) += rhs; }template<i64 M>ModIntT<M> operator+(ModIntT<M> lhs, i64 rhs) { return ModIntT<M>(lhs) += rhs; }template<i64 M>ModIntT<M> operator+(i64 lhs, ModIntT<M> rhs) { return ModIntT<M>(rhs) += lhs; }template<i64 M>ModIntT<M> operator-(ModIntT<M> lhs, ModIntT<M> rhs) { return ModIntT<M>(lhs) -= rhs; }template<i64 M>ModIntT<M> operator-(ModIntT<M> lhs, i64 rhs) { return ModIntT<M>(lhs) -= rhs; }template<i64 M>ModIntT<M> operator-(i64 lhs, ModIntT<M> rhs) { return ModIntT<M>(rhs) -= lhs; }template<i64 M>ModIntT<M> operator*(ModIntT<M> lhs, ModIntT<M> rhs) { return ModIntT<M>(lhs) *= rhs; }template<i64 M>ModIntT<M> operator*(ModIntT<M> lhs, i64 rhs) { return ModIntT<M>(lhs) *= rhs; }template<i64 M>ModIntT<M> operator*(i64 lhs, ModIntT<M> rhs) { return ModIntT<M>(rhs) *= lhs; }template<i64 M>bool operator==(ModIntT<M> lhs, ModIntT<M> rhs) { return lhs.v_ == rhs.v_; }template<i64 M>bool operator==(ModIntT<M> lhs, i64 rhs) { return lhs == ModIntT<M>(rhs); }template<i64 M>bool operator==(i64 lhs, ModIntT<M> rhs) { return ModIntT<M>(lhs) == rhs; }template<i64 M>bool operator!=(ModIntT<M> lhs, ModIntT<M> rhs) { return !(lhs == rhs); }template<i64 M>bool operator!=(ModIntT<M> lhs, i64 rhs) { return !(lhs == rhs); }template<i64 M>bool operator!=(i64 lhs, ModIntT<M> rhs) { return !(lhs == rhs); }template<i64 M>struct Scan<ModIntT<M>> {static ModIntT<M> scan(istream& in) {return Scan<i64>::scan(in);}};template<i64 M>struct Fmt<ModIntT<M>> {static void fmt(ostream& out, ModIntT<M> x) {fmt_write(out, x.v_);}};template<i64 M>struct Dbg<ModIntT<M>> {static void dbg(ostream& out, ModIntT<M> x) {dbg_write(out, x.v_);}};using ModInt = ModIntT<MOD>;// }}}// }}}// init {{{struct ProconInit {static constexpr int IOS_PREC = 15;static constexpr bool AUTOFLUSH = false;ProconInit() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(IOS_PREC);#ifdef PROCON_LOCALcin.exceptions(ios::failbit | ios::badbit);cerr << fixed << setprecision(IOS_PREC);#endifif(AUTOFLUSH)cout << unitbuf;}} PROCON_INIT;// }}}//--------------------------------------------------------------------constexpr i64 TABLE[] {1,641102369,578095319,5832229,259081142,974067448,316220877,690120224,251368199,980250487,682498929,134623568,95936601,933097914,167332441,598816162,336060741,248744620,626497524,288843364,491101308,245341950,565768255,246899319,968999,586350670,638587686,881746146,19426633,850500036,76479948,268124147,842267748,886294336,485348706,463847391,544075857,898187927,798967520,82926604,723816384,156530778,721996174,299085602,323604647,172827403,398699886,530389102,294587621,813805606,67347853,497478507,196447201,722054885,228338256,407719831,762479457,746536789,811667359,778773518,27368307,438371670,59469516,5974669,766196482,606322308,86609485,889750731,340941507,371263376,625544428,788878910,808412394,996952918,585237443,1669644,361786913,480748381,595143852,837229828,199888908,526807168,579691190,145404005,459188207,534491822,439729802,840398449,899297830,235861787,888050723,656116726,736550105,440902696,85990869,884343068,56305184,973478770,168891766,804805577,927880474,876297919,934814019,676405347,567277637,112249297,44930135,39417871,47401357,108819476,281863274,60168088,692636218,432775082,14235602,770511792,400295761,697066277,421835306,220108638,661224977,261799937,168203998,802214249,544064410,935080803,583967898,211768084,751231582,972424306,623534362,335160196,243276029,554749550,60050552,797848181,395891998,172428290,159554990,887420150,970055531,250388809,487998999,856259313,82104855,232253360,513365505,244109365,1559745,695345956,261384175,849009131,323214113,747664143,444090941,659224434,80729842,570033864,664989237,827348878,195888993,576798521,457882808,731551699,212938473,509096183,827544702,678320208,677711203,289752035,66404266,555972231,195290384,97136305,349551356,785113347,83489485,66247239,52167191,307390891,547665832,143066173,350016754,917404120,296269301,996122673,23015220,602139210,748566338,187348575,109838563,574053420,105574531,304173654,542432219,34538816,325636655,437843114,630621321,26853683,933245637,616368450,238971581,511371690,557301633,911398531,848952161,958992544,925152039,914456118,724691727,636817583,238087006,946237212,910291942,114985663,492237273,450387329,834860913,763017204,368925948,475812562,740594930,45060610,806047532,464456846,172115341,75307702,116261993,562519302,268838846,173784895,243624360,61570384,481661251,938269070,95182730,91068149,115435332,495022305,136026497,506496856,710729672,113570024,366384665,564758715,270239666,277118392,79874094,702807165,112390913,730341625,103056890,677948390,339464594,167240465,108312174,839079953,479334442,271788964,135498044,277717575,591048681,811637561,353339603,889410460,839849206,192345193,736265527,316439118,217544623,788132977,618898635,183011467,380858207,996097969,898554793,335353644,54062950,611251733,419363534,965429853,160398980,151319402,990918946,607730875,450718279,173539388,648991369,970937898,500780548,780122909,39052406,276894233,460373282,651081062,461415770,358700839,643638805,560006119,668123525,686692315,673464765,957633609,199866123,563432246,841799766,385330357,504962686,954061253,128487469,685707545,299172297,717975101,577786541,318951960,773206631,306832604,204355779,573592106,30977140,450398100,363172638,258379324,472935553,93940075,587220627,776264326,793270300,291733496,522049725,579995261,335416359,142946099,472012302,559947225,332139472,499377092,464599136,164752359,309058615,86117128,580204973,563781682,954840109,624577416,895609896,888287558,836813268,926036911,386027524,184419613,724205533,403351886,715247054,716986954,830567832,383388563,68409439,6734065,189239124,68322490,943653305,405755338,811056092,179518046,825132993,343807435,985084650,868553027,148528617,160684257,882148737,591915968,701445829,529726489,302177126,974886682,241107368,798830099,940567523,11633075,325334066,346091869,115312728,473718967,218129285,878471898,180002392,699739374,917084264,856859395,435327356,808651347,421623838,105419548,59883031,322487421,79716267,715317963,429277690,398078032,316486674,384843585,940338439,937409008,940524812,947549662,833550543,593524514,996164327,987314628,697611981,636177449,274192146,418537348,925347821,952831975,893732627,1277567,358655417,141866945,581830879,987597705,347046911,775305697,125354499,951540811,247662371,343043237,568392357,997474832,209244402,380480118,149586983,392838702,309134554,990779998,263053337,325362513,780072518,551028176,990826116,989944961,155569943,596737944,711553356,268844715,451373308,379404150,462639908,961812918,654611901,382776490,41815820,843321396,675258797,845583555,934281721,741114145,275105629,666247477,325912072,526131620,252551589,432030917,554917439,818036959,754363835,795190182,909210595,278704903,719566487,628514947,424989675,321685608,50590510,832069712,198768464,702004730,99199382,707469729,747407118,302020341,497196934,5003231,726997875,382617671,296229203,183888367,703397904,552133875,732868367,350095207,26031303,863250534,216665960,561745549,352946234,784139777,733333339,503105966,459878625,803187381,16634739,180898306,68718097,985594252,404206040,749724532,97830135,611751357,31131935,662741752,864326453,864869025,167831173,559214642,718498895,91352335,608823837,473379392,385388084,152267158,681756977,46819124,313132653,56547945,442795120,796616594,256141983,152028387,636578562,385377759,553033642,491415383,919273670,996049638,326686486,160150665,141827977,540818053,693305776,593938674,186576440,688809790,565456578,749296077,519397500,551096742,696628828,775025061,370732451,164246193,915265013,457469634,923043932,912368644,777901604,464118005,637939935,956856710,490676632,453019482,462528877,502297454,798895521,100498586,699767918,849974789,811575797,438952959,606870929,907720182,179111720,48053248,508038818,811944661,752550134,401382061,848924691,764368449,34629406,529840945,435904287,26011548,208184231,446477394,206330671,366033520,131772368,185646898,648711554,472759660,523696723,271198437,25058942,859369491,817928963,330711333,724464507,437605233,701453022,626663115,281230685,510650790,596949867,295726547,303076380,465070856,272814771,538771609,48824684,951279549,939889684,564188856,48527183,201307702,484458461,861754542,326159309,181594759,668422905,286273596,965656187,44135644,359960756,936229527,407934361,267193060,456152084,459116722,124804049,262322489,920251227,816929577,483924582,151834896,167087470,490222511,903466878,361583925,368114731,339383292,388728584,218107212,249153339,909458706,322908524,202649964,92255682,573074791,15570863,94331513,744158074,196345098,334326205,9416035,98349682,882121662,769795511,231988936,888146074,137603545,582627184,407518072,919419361,909433461,986708498,310317874,373745190,263645931,256853930,876379959,702823274,147050765,308186532,175504139,180350107,797736554,606241871,384547635,273712630,586444655,682189174,666493603,946867127,819114541,502371023,261970285,825871994,126925175,701506133,314738056,341779962,561011609,815463367,46765164,49187570,188054995,957939114,64814326,933376898,329837066,338121343,765215899,869630152,978119194,632627667,975266085,435887178,282092463,129621197,758245605,827722926,201339230,918513230,322096036,547838438,985546115,852304035,593090119,689189630,555842733,567033437,469928208,212842957,117842065,404149413,155133422,663307737,208761293,206282795,717946122,488906585,414236650,280700600,962670136,534279149,214569244,375297772,811053196,922377372,289594327,219932130,211487466,701050258,398782410,863002719,27236531,217598709,375472836,810551911,178598958,247844667,676526196,812283640,863066876,857241854,113917835,624148346,726089763,564827277,826300950,478982047,439411911,454039189,633292726,48562889,802100365,671734977,945204804,508831870,398781902,897162044,644050694,892168027,828883117,277714559,713448377,624500515,590098114,808691930,514359662,895205045,715264908,628829100,484492064,919717789,513196123,748510389,403652653,574455974,77123823,172096141,819801784,581418893,15655126,15391652,875641535,203191898,264582598,880691101,907800444,986598821,340030191,264688936,369832433,785804644,842065079,423951674,663560047,696623384,496709826,161960209,331910086,541120825,951524114,841656666,162683802,629786193,190395535,269571439,832671304,76770272,341080135,421943723,494210290,751040886,317076664,672850561,72482816,493689107,135625240,100228913,684748812,639655136,906233141,929893103,277813439,814362881,562608724,406024012,885537778,10065330,60625018,983737173,60517502,551060742,804930491,823845496,727416538,946421040,678171399,842203531,175638827,894247956,538609927,885362182,946464959,116667533,749816133,241427979,871117927,281804989,163928347,563796647,640266394,774625892,59342705,256473217,674115061,918860977,322633051,753513874,393556719,304644842,767372800,161362528,754787150,627655552,677395736,799289297,846650652,816701166,687265514,787113234,358757251,701220427,607715125,245795606,600624983,10475577,728620948,759404319,36292292,491466901,22556579,114495791,647630109,586445753,482254337,718623833,763514207,66547751,953634340,351472920,308474522,494166907,634359666,172114298,865440961,364380585,921648059,965683742,260466949,117483873,962540888,237120480,620531822,193781724,213092254,107141741,602742426,793307102,756154604,236455213,362928234,14162538,753042874,778983779,25977209,49389215,698308420,859637374,49031023,713258160,737331920,923333660,804861409,83868974,682873215,217298111,883278906,176966527,954913,105359006,390019735,10430738,706334445,315103615,567473423,708233401,48160594,946149627,346966053,281329488,462880311,31503476,185438078,965785236,992656683,916291845,881482632,899946391,321900901,512634493,303338827,121000338,967284733,492741665,152233223,165393390,680128316,917041303,532702135,741626808,496442755,536841269,131384366,377329025,301196854,859917803,676511002,373451745,847645126,823495900,576368335,73146164,954958912,847549272,241289571,646654592,216046746,205951465,3258987,780882948,822439091,598245292,869544707,698611116,};constexpr i64 D = 1000000;void solve() {i64 N = RD();if(N >= MOD) {PRINTLN(0);return;}i64 q = N / D;ModInt ans = TABLE[q];FOR(i, D*q+1, N+1) {ans *= i;}PRINTLN(ans);}signed main() {solve();return 0;}