結果
| 問題 |
No.502 階乗を計算するだけ
|
| ユーザー |
 maspy
|
| 提出日時 | 2022-04-15 23:47:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 29,119 bytes |
| コンパイル時間 | 1,848 ms |
| コンパイル使用メモリ | 200,864 KB |
| 最終ジャッジ日時 | 2025-01-28 18:44:30 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 46 WA * 6 |
ソースコード
#line 1 "/home/maspy/compro/library/my_template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define vv(type, name, h, ...) \
vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) \
vector<vector<vector<type>>> name( \
h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name( \
a, vector<vector<vector<type>>>( \
b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define FOR_(n) for (ll _ = 0; (_) < (ll)(n); ++(_))
#define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i))
#define FOR3(i, m, n) for (ll i = (m); (i) < (ll)(n); ++(i))
#define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i))
#define FOR3_R(i, m, n) for (ll i = (ll)(n)-1; (i) >= (ll)(m); --(i))
#define FOR_subset(t, s) for (ll t = s; t >= 0; t = (t == 0 ? -1 : (t - 1) & s))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
template <typename T>
T SUM(vector<T> &A) {
T sum = T(0);
for (auto &&a: A) sum += a;
return sum;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
template <typename T, typename U>
T ceil(T x, U y) {
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T, typename U>
pair<T, T> divmod(T x, U y) {
T q = floor(x, y);
return {q, x - q * y};
}
ll binary_search(function<bool(ll)> check, ll ok, ll ng) {
assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
if (check(x))
ok = x;
else
ng = x;
}
return ok;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
vi s_to_vi(string S, char first_char = 'a') {
vi A(S.size());
FOR(i, S.size()) { A[i] = S[i] - first_char; }
return A;
}
template <typename T>
vector<T> cumsum(vector<T> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
template <typename T, typename CNT = int>
vc<CNT> bincount(vc<T> &A, int size) {
vc<CNT> C(size);
for (auto &&x: A) { ++C[x]; }
return C;
}
template <typename T>
vector<int> argsort(vector<T> &A) {
// stable
vector<int> ids(A.size());
iota(all(ids), 0);
sort(all(ids),
[&](int i, int j) { return A[i] < A[j] || (A[i] == A[j] && i < j); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
int n = len(A);
assert(len(I) == n);
vc<T> B(n);
FOR(i, n) B[i] = A[I[i]];
return B;
}
#line 1 "/home/maspy/compro/library/other/io.hpp"
// based on yosupo's fastio
#include <unistd.h>
namespace detail {
template <typename T, decltype(&T::is_modint) = &T::is_modint>
std::true_type check_value(int);
template <typename T>
std::false_type check_value(long);
} // namespace detail
template <typename T>
struct is_modint : decltype(detail::check_value<T>(0)) {};
template <typename T>
using is_modint_t = enable_if_t<is_modint<T>::value>;
template <typename T>
using is_not_modint_t = enable_if_t<!is_modint<T>::value>;
struct Scanner {
FILE *fp;
char line[(1 << 15) + 1];
size_t st = 0, ed = 0;
void reread() {
memmove(line, line + st, ed - st);
ed -= st;
st = 0;
ed += fread(line + ed, 1, (1 << 15) - ed, fp);
line[ed] = '\0';
}
bool succ() {
while (true) {
if (st == ed) {
reread();
if (st == ed) return false;
}
while (st != ed && isspace(line[st])) st++;
if (st != ed) break;
}
if (ed - st <= 50) {
bool sep = false;
for (size_t i = st; i < ed; i++) {
if (isspace(line[i])) {
sep = true;
break;
}
}
if (!sep) reread();
}
return true;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
while (true) {
size_t sz = 0;
while (st + sz < ed && !isspace(line[st + sz])) sz++;
ref.append(line + st, sz);
st += sz;
if (!sz || st != ed) break;
reread();
}
return true;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
ref = T(0);
while (isdigit(line[st])) { ref = 10 * ref + (line[st++] & 0xf); }
if (neg) ref = -ref;
return true;
}
template <class T, is_modint_t<T> * = nullptr>
bool read_single(T &ref) {
long long val = 0;
bool f = read_single(val);
ref = T(val);
return f;
}
bool read_single(double &ref) {
string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
bool read_single(char &ref) {
string s;
if (!read_single(s) || s.size() != 1) return false;
ref = s[0];
return true;
}
template <class T>
bool read_single(vector<T> &ref) {
for (auto &d: ref) {
if (!read_single(d)) return false;
}
return true;
}
template <class T, class U>
bool read_single(pair<T, U> &p) {
return (read_single(p.first) && read_single(p.second));
}
template <class A, class B, class C>
bool read_single(tuple<A, B, C> &p) {
return (read_single(get<0>(p)) && read_single(get<1>(p))
&& read_single(get<2>(p)));
}
template <class A, class B, class C, class D>
bool read_single(tuple<A, B, C, D> &p) {
return (read_single(get<0>(p)) && read_single(get<1>(p))
&& read_single(get<2>(p)) && read_single(get<3>(p)));
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
Scanner(FILE *fp) : fp(fp) {}
};
struct Printer {
Printer(FILE *_fp) : fp(_fp) {}
~Printer() { flush(); }
static constexpr size_t SIZE = 1 << 15;
FILE *fp;
char line[SIZE], small[50];
size_t pos = 0;
void flush() {
fwrite(line, 1, pos, fp);
pos = 0;
}
void write(const char &val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
void write(T val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write('0');
return;
}
if (val < 0) {
write('-');
val = -val; // todo min
}
size_t len = 0;
while (val) {
small[len++] = char(0x30 | (val % 10));
val /= 10;
}
for (size_t i = 0; i < len; i++) { line[pos + i] = small[len - 1 - i]; }
pos += len;
}
void write(const string &s) {
for (char c: s) write(c);
}
void write(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write(s[i]);
}
void write(const double &x) {
ostringstream oss;
oss << setprecision(15) << x;
string s = oss.str();
write(s);
}
void write(const long double &x) {
ostringstream oss;
oss << setprecision(15) << x;
string s = oss.str();
write(s);
}
template <class T, is_modint_t<T> * = nullptr>
void write(T &ref) {
write(ref.val);
}
template <class T>
void write(const vector<T> &val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
template <class T, class U>
void write(const pair<T, U> &val) {
write(val.first);
write(' ');
write(val.second);
}
template <class A, class B, class C>
void write(const tuple<A, B, C> &val) {
auto &[a, b, c] = val;
write(a);
write(' ');
write(b);
write(' ');
write(c);
}
template <class A, class B, class C, class D>
void write(const tuple<A, B, C, D> &val) {
auto &[a, b, c, d] = val;
write(a);
write(' ');
write(b);
write(' ');
write(c);
write(' ');
write(d);
}
template <class T, size_t S>
void write(const array<T, S> &val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
void write(i128 val) {
string s;
bool negative = 0;
if(val < 0){
negative = 1;
val = -val;
}
while (val) {
s += '0' + int(val % 10);
val /= 10;
}
if(negative) s += "-";
reverse(all(s));
if (len(s) == 0) s = "0";
write(s);
}
};
Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);
void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
printer.write(head);
if (sizeof...(Tail)) printer.write(' ');
print(forward<Tail>(tail)...);
}
void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &... tail) {
scanner.read(head);
read(tail...);
}
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 2 "/home/maspy/compro/library/mod/modint.hpp"
template <u32 mod>
struct modint {
static constexpr bool is_modint = true;
u32 val;
constexpr modint(const ll val = 0) noexcept
: val(val >= 0 ? val % mod : (mod - (-val) % mod) % mod) {}
bool operator<(const modint &other) const {
return val < other.val;
} // To use std::map
modint &operator+=(const modint &p) {
if ((val += p.val) >= mod) val -= mod;
return *this;
}
modint &operator-=(const modint &p) {
if ((val += mod - p.val) >= mod) val -= mod;
return *this;
}
modint &operator*=(const modint &p) {
val = (u32)(1LL * val * p.val % mod);
return *this;
}
modint &operator/=(const modint &p) {
*this *= p.inverse();
return *this;
}
modint operator-() const { return modint(get_mod() - val); }
modint operator+(const modint &p) const { return modint(*this) += p; }
modint operator-(const modint &p) const { return modint(*this) -= p; }
modint operator*(const modint &p) const { return modint(*this) *= p; }
modint operator/(const modint &p) const { return modint(*this) /= p; }
bool operator==(const modint &p) const { return val == p.val; }
bool operator!=(const modint &p) const { return val != p.val; }
modint inverse() const {
int a = val, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b), swap(u -= t * v, v);
}
return modint(u);
}
modint pow(int64_t n) const {
modint ret(1), mul(val);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
static constexpr u32 get_mod() { return mod; }
};
struct ArbitraryModInt {
static constexpr bool is_modint = true;
u32 val;
ArbitraryModInt() : val(0) {}
ArbitraryModInt(int64_t y)
: val(y >= 0 ? y % get_mod()
: (get_mod() - (-y) % get_mod()) % get_mod()) {}
bool operator<(const ArbitraryModInt &other) const {
return val < other.val;
} // To use std::map<ArbitraryModInt, T>
static u32 &get_mod() {
static u32 mod = 0;
return mod;
}
static void set_mod(int md) { get_mod() = md; }
ArbitraryModInt &operator+=(const ArbitraryModInt &p) {
if ((val += p.val) >= get_mod()) val -= get_mod();
return *this;
}
ArbitraryModInt &operator-=(const ArbitraryModInt &p) {
if ((val += get_mod() - p.val) >= get_mod()) val -= get_mod();
return *this;
}
ArbitraryModInt &operator*=(const ArbitraryModInt &p) {
unsigned long long a = (unsigned long long)val * p.val;
unsigned xh = (unsigned)(a >> 32), xl = (unsigned)a, d, m;
asm("divl %4; \n\t" : "=a"(d), "=d"(m) : "d"(xh), "a"(xl), "r"(get_mod()));
val = m;
return *this;
}
ArbitraryModInt &operator/=(const ArbitraryModInt &p) {
*this *= p.inverse();
return *this;
}
ArbitraryModInt operator-() const { return ArbitraryModInt(get_mod() - val); }
ArbitraryModInt operator+(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) += p;
}
ArbitraryModInt operator-(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) -= p;
}
ArbitraryModInt operator*(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) *= p;
}
ArbitraryModInt operator/(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) /= p;
}
bool operator==(const ArbitraryModInt &p) const { return val == p.val; }
bool operator!=(const ArbitraryModInt &p) const { return val != p.val; }
ArbitraryModInt inverse() const {
int a = val, b = get_mod(), u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b), swap(u -= t * v, v);
}
return ArbitraryModInt(u);
}
ArbitraryModInt pow(int64_t n) const {
ArbitraryModInt ret(1), mul(val);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
};
template <typename mint>
tuple<mint, mint, mint> get_factorial_data(int n) {
static constexpr int mod = mint::get_mod();
assert(0 <= n && n < mod);
static vector<mint> fact = {1, 1};
static vector<mint> fact_inv = {1, 1};
static vector<mint> inv = {0, 1};
while (len(fact) <= n) {
int k = len(fact);
fact.eb(fact[k - 1] * mint(k));
auto q = ceil(mod, k);
int r = k * q - mod;
inv.eb(inv[r] * mint(q));
fact_inv.eb(fact_inv[k - 1] * inv[k]);
}
return {fact[n], fact_inv[n], inv[n]};
}
template <typename mint>
mint fact(int n) {
static constexpr int mod = mint::get_mod();
assert(0 <= n);
if (n >= mod) return 0;
return get<0>(get_factorial_data<mint>(n));
}
template <typename mint>
mint fact_inv(int n) {
static constexpr int mod = mint::get_mod();
assert(0 <= n && n < mod);
return get<1>(get_factorial_data<mint>(n));
}
template <typename mint>
mint inv(int n) {
static constexpr int mod = mint::get_mod();
assert(0 <= n && n < mod);
return get<2>(get_factorial_data<mint>(n));
}
template <typename mint>
mint C(ll n, ll k, bool large = false) {
assert(n >= 0);
if (k < 0 || n < k) return 0;
if (!large) return fact<mint>(n) * fact_inv<mint>(k) * fact_inv<mint>(n - k);
k = min(k, n - k);
mint x(1);
FOR(i, k) { x *= mint(n - i); }
x *= fact_inv<mint>(k);
return x;
}
using modint107 = modint<1000000007>;
using modint998 = modint<998244353>;
using amint = ArbitraryModInt;
#line 4 "main.cpp"
// 1<<20
int fact107table[1024] = {
1, 55098162, 799018112, 644524227, 804570289, 699421653, 999080403,
347644092, 298264049, 547915206, 68604898, 242165296, 99769214, 860919687,
695517422, 304751648, 800304985, 404296372, 345504787, 346396697, 661521818,
811907079, 150066936, 379369971, 383295467, 935785718, 884263687, 185573413,
564595064, 703180737, 200891912, 45268585, 361946029, 862561983, 555223579,
717470752, 742784681, 818749011, 825255985, 753131797, 774984247, 244818236,
509057662, 323909107, 486700580, 791867040, 303567866, 976227856, 944323045,
513842788, 567328309, 686789145, 441779759, 195814622, 2372115, 135277835,
294954750, 723496015, 119271996, 986547466, 717213282, 842873786, 234208469,
864111391, 117175975, 118474328, 890000195, 504224423, 508111147, 725796711,
802878396, 246336953, 468479803, 310148765, 702396285, 576460826, 175957429,
883569154, 610938868, 287010876, 212131504, 438039362, 359800384, 432795594,
633410554, 155137408, 314936343, 179257123, 943713322, 673162662, 422288605,
545194215, 158939936, 115503469, 689488055, 401702717, 532814826, 592763273,
773200138, 474494844, 496413916, 528795782, 353056535, 193856493, 974131920,
921613963, 393169150, 830738748, 837700032, 174096350, 803328680, 434966400,
698398808, 589644499, 669724987, 860591235, 921625212, 16363628, 511768062,
515388641, 946983274, 375285964, 288822198, 841563728, 550332445, 512378200,
723231171, 688050346, 638916270, 303773384, 338440254, 794857710, 983752474,
388318097, 628785057, 576616801, 25029917, 915971206, 534292228, 562759338,
78040824, 844961917, 391581518, 37735563, 166114276, 533068572, 866703952,
971782310, 839681504, 713554826, 626185157, 514984174, 485251798, 656102354,
587843669, 710027943, 85325823, 3718675, 780721779, 888259006, 709912685,
458901728, 526677538, 873562554, 28552679, 273046452, 694930680, 19258350,
633408320, 497294065, 699279305, 863781574, 941853248, 754504516, 567820050,
153017173, 309672260, 864251395, 999648212, 504204977, 139941702, 735693996,
475650352, 751284240, 61380201, 358232497, 650878822, 427480644, 552589593,
7500105, 216677699, 848980694, 565479858, 273508588, 466692797, 613411243,
300912167, 686394608, 943827276, 838125279, 585515687, 370926564, 947737740,
905550006, 780384258, 985335993, 380437817, 436417804, 952004841, 168955240,
310513812, 254079069, 734838326, 209059985, 189848103, 178192696, 239063132,
724829800, 471021218, 22656326, 940110791, 670514782, 160800189, 60164301,
534784668, 623973502, 444037086, 781751482, 292944263, 109226380, 542920902,
293050078, 501265668, 293547492, 678045668, 870103700, 199000138, 973807329,
712358272, 567141781, 667220314, 930560330, 520238050, 188798676, 915219645,
875218552, 107463226, 924068096, 373354885, 161687663, 742633209, 899649882,
172223561, 490032230, 532248036, 733461058, 864357307, 39004186, 666796032,
19300991, 866949601, 152723250, 632980031, 28154382, 812475803, 342290061,
378814433, 311792214, 811932026, 628385664, 925729472, 483891986, 104909388,
838245993, 226415225, 80497756, 905742254, 760776367, 59951296, 502463774,
432422968, 529614143, 987845867, 941009243, 680208181, 129640287, 135701022,
93697263, 580002085, 736790935, 647149348, 963929930, 456358064, 393498474,
345303775, 836988638, 663009951, 688270876, 821556726, 61653598, 10436780,
40516807, 602622268, 365808294, 624854174, 764883550, 133418712, 979879958,
883675628, 802594907, 960259381, 657818185, 789571797, 869941376, 925271608,
584915231, 373203547, 780879573, 162303580, 219381059, 988122582, 809692587,
524697206, 890686281, 255441194, 208655553, 818176738, 234316848, 355059206,
328134956, 168206574, 937157388, 816978580, 176422569, 755437061, 653448585,
104372309, 277493780, 817870252, 509736736, 467977765, 33347068, 537441964,
30292019, 828581950, 303478168, 255296787, 226318316, 205744264, 27632923,
92186650, 148892391, 626052914, 122285044, 885244951, 369494295, 227491286,
978201674, 280638485, 366898179, 400916139, 936093782, 457514504, 799178457,
77262843, 887662440, 311502312, 433979195, 62200437, 841399346, 399849157,
55933275, 269778121, 314076684, 346937429, 587781485, 403077288, 120051495,
341462465, 804288108, 354008902, 773347166, 273225862, 977284051, 711403642,
332515431, 72546287, 70463395, 383292501, 583203296, 58684392, 59801553,
934861184, 123659858, 172225366, 16490486, 640104831, 651484064, 414057597,
912563140, 516388569, 982284977, 354948305, 845441532, 249139343, 112170128,
852836789, 363141564, 95948290, 593351477, 538225430, 684921161, 437291872,
753187673, 197482933, 175217286, 930569788, 733325632, 206283594, 860092876,
264612104, 375479413, 433058282, 824726232, 663285168, 610355794, 410260572,
141034667, 801620565, 280447634, 539012567, 582334448, 117111267, 192909957,
901437820, 242191138, 473245986, 119617826, 582524622, 27271548, 763258578,
517785257, 740102975, 807353604, 677357433, 502074113, 763360936, 37227708,
928062158, 453067630, 416392863, 403468924, 390966467, 90780688, 97580941,
397618185, 444801884, 718494493, 905625902, 439144581, 809645601, 571259258,
311262977, 379698006, 619843354, 42160512, 709478648, 139908674, 884941258,
7778675, 277356393, 574397869, 64807900, 568439116, 884254362, 793527033,
634827367, 242270229, 166836929, 699666005, 782871805, 430576594, 69423864,
551852289, 854389404, 33130302, 690600649, 389114637, 594444305, 378027483,
501626534, 769371462, 565727105, 185366687, 760889594, 622679145, 531967768,
895838088, 631099033, 636979633, 966288648, 722632929, 487185734, 674289231,
978197320, 42219437, 631006005, 62801370, 477869560, 150370443, 708309474,
569052485, 373979365, 110651678, 526192057, 1187964, 604094093, 92402540,
199407377, 263950464, 85094825, 143055746, 488295779, 242448163, 271952450,
88191394, 640214992, 291887361, 38760888, 143069496, 957354294, 970267065,
791944735, 188497194, 644438434, 778147734, 540003575, 909162269, 307294631,
117326469, 318009725, 133188612, 150701170, 968756181, 75908005, 226593925,
597645956, 881933480, 899459287, 455981899, 229221768, 807672432, 414097149,
643328910, 465859747, 254429407, 523184583, 71216457, 323329780, 538880177,
339599190, 794248796, 185173563, 244936068, 257855397, 449978612, 725702638,
935779255, 177430235, 442849413, 379319626, 300751979, 635487273, 183449414,
5934499, 378785317, 861919911, 678817974, 268409923, 203403445, 572871951,
443809175, 295389783, 505988742, 840133940, 846932417, 746139508, 669216033,
75861584, 858480227, 466369788, 200782437, 410124462, 398817445, 968382032,
980738344, 56008451, 983178362, 179562483, 823724361, 469703761, 906401712,
312400795, 531915860, 313966891, 499155799, 188116091, 542673699, 973727253,
756116696, 555496689, 953139148, 664729273, 301347505, 874894370, 769419863,
39619555, 844221994, 437468538, 567165362, 826223750, 237919972, 889742229,
340395341, 391452566, 470281592, 861327653, 391319516, 846903225, 165819062,
626164401, 316709929, 521538790, 990712756, 973874818, 890738343, 563978092,
109958482, 828180512, 763297389, 963971145, 754096813, 773609544, 459522164,
8038398, 631562195, 353217532, 305814226, 567542439, 895416683, 84833664,
222068809, 137353990, 316612885, 847273944, 686340505, 587953096, 891163150,
312873714, 170456823, 499030076, 552288670, 984000707, 296655021, 907848089,
795824037, 868241961, 731318793, 613986016, 504817890, 831254264, 714194680,
892153437, 432990870, 213690618, 820549872, 68492073, 905288570, 828076972,
100771571, 701929895, 429147966, 855717720, 702005759, 834355402, 271364955,
808645569, 975796499, 767810085, 630847407, 570582799, 453848037, 305413582,
658578009, 72025782, 432456806, 679768447, 209753914, 642309814, 367985447,
648596045, 662634665, 934081491, 20395923, 976333508, 947778280, 290901114,
683388002, 527020810, 977326275, 488693383, 189698098, 419374780, 110616851,
127872982, 575257710, 581134348, 809887616, 616715986, 785224788, 330000241,
549806410, 300312979, 453241111, 120873512, 806993146, 171910094, 251834489,
979979771, 418698259, 752813751, 394025833, 29105970, 80840916, 796020902,
589114561, 204474745, 376387134, 234987470, 80775688, 766942711, 782094550,
251204403, 958598099, 73582601, 425563446, 280068465, 830973501, 760007127,
289646156, 209940903, 843351800, 279527279, 738627148, 205145989, 347868746,
12854961, 648847391, 11192482, 203518335, 83599363, 614624895, 760355983,
241204239, 725553388, 423530890, 233709513, 129164025, 183143523, 474024463,
587482677, 262947835, 830758485, 490545965, 42715938, 774365958, 917430364,
848838405, 184884783, 363325662, 815621393, 13287526, 130498889, 568838029,
994918408, 689158356, 514272481, 755554988, 448513470, 717322665, 827827457,
350229871, 213613603, 814952584, 154931117, 596054309, 996378663, 464177580,
523761543, 498980428, 224645330, 774166263, 755880313, 389249660, 81743329,
776397644, 662396499, 223245698, 916069463, 500419874, 906869272, 990436276,
83413835, 861165195, 955992714, 931625913, 809913797, 990584878, 385913422,
976567861, 988873023, 385236984, 677028085, 265052939, 959365279, 418677004,
258798519, 676383755, 636025853, 270238386, 206316099, 239739022, 885152995,
473139022, 930824994, 355594287, 876223850, 584874216, 450993348, 250278273,
66731334, 677818083, 932165316, 513087030, 595832582, 266493735, 941688056,
358758739, 118809938, 109331276, 935297327, 907221850, 844856226, 966689708,
153251680, 426805713, 872205902, 228749156, 852770211, 253065643, 265234802,
21716397, 785998921, 576621647, 514060757, 602374495, 488838351, 959753273,
105481283, 471659303, 687019929, 675067970, 650147251, 384820796, 572532868,
616933893, 598368862, 955007801, 991174700, 162133698, 58160791, 148888347,
464964795, 922938492, 89012579, 110574373, 388391339, 378503165, 317247776,
8038731, 656691478, 44251737, 780947050, 9218625, 591467905, 660897916,
894672548, 927151139, 575483441, 12732642, 292282890, 535590986, 602061256,
105810330, 549519899, 900104648, 428472182, 404847041, 747230327, 464453245,
284822208, 7040213, 767161925, 268629370, 892069143, 822121223, 971455916,
221846561, 64553306, 769796929, 675275231, 652246661, 449517151, 975374186,
994429602, 299117212, 782066823, 100306236, 683957845, 778001329, 951091055,
742690935, 735367617, 614080637, 290990048, 34499833, 990980489, 559407811,
525864614, 317820378, 806036323, 701425752, 761690151, 688462290, 373529632,
32050577, 719463331, 118313951, 999322637, 97750199, 523426443, 819087263,
545301062, 488598090, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0};
int fact107(int n) {
constexpr int mod = modint107::get_mod();
if (n >= mod) return 0;
auto [q, r] = divmod(n, 1 << 20);
ll x = fact107table[q];
int s = q << 20;
FOR(i, r) x = x * (s + i + 1) % mod;
return x;
}
void solve() {
LL(N);
print(fact107(N));
}
signed main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << setprecision(15);
ll T = 1;
// LL(T);
FOR(_, T) solve();
return 0;
}