#line 2 "/home/cocojapanpan/Procon_CPP/proconLibrary/lib/template/procon.hpp" #ifndef DEBUG // 提出時にassertはオフ #ifndef NDEBUG #define NDEBUG #endif // 定数倍高速化 #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include using namespace std; using ll = long long; #define ALL(x) (x).begin(), (x).end() template using vec = vector; template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } template constexpr T INF = 1'000'000'000; template <> constexpr int INF = 1'000'000'000; template <> constexpr ll INF = ll(INF) * INF * 2; #line 2 "/home/cocojapanpan/Procon_CPP/proconLibrary/lib/modint/modint_static.hpp" #line 2 "/home/cocojapanpan/Procon_CPP/proconLibrary/lib/modint/innermath_modint.hpp" #line 4 "/home/cocojapanpan/Procon_CPP/proconLibrary/lib/modint/innermath_modint.hpp" namespace innermath_modint{ using ll = long long; using ull = unsigned long long; // xのmodを[0, mod)で返す constexpr ll safe_mod(ll x, ll mod) { x %= mod; if (x < 0) x += mod; return x; } constexpr ll pow_mod_constexpr(ll x, ll n, ll mod) { if (mod == 1) return 0; ll ret = 1; ll beki = safe_mod(x, mod); while (n) { // LSBから順に見る if (n & 1) { ret = (ret * beki) % mod; } beki = (beki * beki) % mod; n >>= 1; } return ret; } // int型(2^32以下)の高速な素数判定 constexpr bool is_prime_constexpr(int n) { if (n <= 1) return false; if (n == 2 || n == 7 || n == 61) return true; if (n % 2 == 0) return false; // ミラーラビン判定 int型ならa={2,7,61}で十分 constexpr ll bases[] = {2, 7, 61}; // n-1 = 2^r * d ll d = n - 1; while (d % 2 == 0) d >>= 1; // 素数modは1の平方根として非自明な解を持たない // つまり非自明な解がある→合成数 for (ll a : bases) { ll t = d; ll y = pow_mod_constexpr(a, t, n); // yが1またはn-1になれば抜ける while (t != n - 1 && y != 1 && y != n - 1) { y = (y * y) % n; t <<= 1; } // 1の平方根として1と-1以外の解(非自明な解)が存在 if (y != n - 1 && t % 2 == 0) { return false; } } return true; } // 拡張ユークリッドの互除法 g = gcd(a,b)と、ax = g (mod b)なる0 <= x < // b/gのペアを返す constexpr std::pair inv_gcd(ll a, ll b) { a = safe_mod(a, b); // aがbの倍数 if (a == 0) return {b, 0}; // 以下 0 <= a < b // [1] s - m0 * a = 0 (mod b) // [2] t - m1 * a = 0 (mod b) // [3] s * |m1| + t * |m0| <= b ll s = b, t = a; ll m0 = 0, m1 = 1; while (t) { // s → s mod t // m0 → m0 - m1 * (s / t) ll u = s / t; s -= t * u; m0 -= m1 * u; { ll tmp = t; t = s; s = tmp; } { ll tmp = m1; m1 = m0; m0 = tmp; } } // s = gcd(a, b) // 終了の直前のステップにおいて // [1] k * s - m0 * a = 0 (mod b) // [2] s - m1 * a = 0 (mod b) // [3] (k * s) * |m1| + s * |m0| <= b // |m0| < b / s if (m0 < 0) m0 += b / s; return {s, m0}; } } #line 5 "/home/cocojapanpan/Procon_CPP/proconLibrary/lib/modint/modint_static.hpp" template struct modint_static { using ll = long long; public: constexpr modint_static(ll x = 0) noexcept : value(x % MOD) { if (value < 0) value += MOD; } constexpr int get_mod() const noexcept { return MOD; } constexpr ll val() const noexcept { return value; } constexpr modint_static operator-() const noexcept { return modint_static(-value); } constexpr modint_static& operator++() noexcept { ++value; if(value == MOD) value = 0; return *this; } constexpr modint_static& operator--() noexcept { if(value == 0) value = MOD; --value; return *this; } constexpr modint_static operator++(int) noexcept { modint_static cpy(*this); ++(*this); return cpy; } constexpr modint_static operator--(int) noexcept { modint_static cpy(*this); --(*this); return cpy; } constexpr modint_static& operator+=(const modint_static& rhs) noexcept { value += rhs.value; if (value >= MOD) value -= MOD; return *this; } constexpr modint_static& operator-=(const modint_static& rhs) noexcept { value += (MOD - rhs.value); if (value >= MOD) value -= MOD; return *this; } constexpr modint_static& operator*=(const modint_static& rhs) noexcept { (value *= rhs.value) %= MOD; // 定数だとコンパイラ最適化がかかる return *this; } constexpr modint_static operator+(const modint_static& rhs) const noexcept { modint_static cpy(*this); return cpy += rhs; } constexpr modint_static operator-(const modint_static& rhs) const noexcept { modint_static cpy(*this); return cpy -= rhs; } constexpr modint_static operator*(const modint_static& rhs) const noexcept { modint_static cpy(*this); return cpy *= rhs; } constexpr modint_static pow(ll beki) const noexcept { modint_static curbekimod(*this); modint_static ret(1); while (beki > 0) { if (beki & 1) ret *= curbekimod; curbekimod *= curbekimod; beki >>= 1; } return ret; } // valueの逆元を求める constexpr modint_static inv() const noexcept { // 拡張ユークリッドの互除法 auto [gcd_value_mod, inv_value] = innermath_modint::inv_gcd(value, MOD); assert(gcd_value_mod == 1); return modint_static(inv_value); } constexpr modint_static& operator/=(const modint_static& rhs) noexcept { return (*this) *= rhs.inv(); } constexpr modint_static operator/(const modint_static& rhs) const noexcept { modint_static cpy(*this); return cpy /= rhs; } private: ll value; }; using mint998244353 = modint_static<998244353>; using mint1000000007 = modint_static<1000000007>; #line 3 "main.cpp" using mint = mint998244353; ll N; vec primeList; map primeFactorized; vec>> divisorsWithFactor{{1, {}}}; map divisorsToIndex; vec dp; void primeEnumerate() { int size = sqrt(N); vec seen(size + 1, false); for(int i = 2; i <= size; i++) { if(seen[i]) continue; primeList.push_back(i); for(int j = i; j <= size; j += i) { seen[j] = true; } } } void primeFactorizeN() { ll curN = N; for(ll prime : primeList) { while(curN % prime == 0) { curN /= prime; ++primeFactorized[prime]; } } if(curN != 1) { ++primeFactorized[curN]; } } void divisorsFactorize(map::iterator curIt) { if(curIt == primeFactorized.end()) return; int size = divisorsWithFactor.size(); ll prime = curIt -> first; int beki = curIt -> second; for(int i = 0; i < size; i++) { ll cur = 1; for(int j = 1; j <= beki; j++) { cur *= prime; ll newNum = divisorsWithFactor[i].first * cur; map newMap = divisorsWithFactor[i].second; newMap[prime] = j; divisorsWithFactor.emplace_back(newNum, newMap); } } divisorsFactorize(next(curIt)); } // debug void printDivisorsFactorized() { for(const pair> &p : divisorsWithFactor) { cerr << p.first << "\n"; for(pair mp : p.second) { cerr << "素因数:" << mp.first << " べき:" << mp.second << "\n"; } } cerr << endl; } void enumerateDivisors(const map &mp, vec &ret) { ret.clear(); ret.push_back(1); for(const pair &p : mp) { int size = ret.size(); ll prime = p.first; for(int i = 0; i < size; i++) { ll cur = 1; for(int j = 1; j <= p.second; j++) { cur *= prime; ret.push_back(ret[i] * cur); } } } } // debug void printDivisors() { vec divisors; enumerateDivisors(divisorsWithFactor.back().second, divisors); for(ll d: divisors) { cerr << d << " "; } cerr << endl; } void compDP() { int size = divisorsWithFactor.size(); dp.assign(size, 0); dp[0] = 1; for(int i = 1; i < size; i++) { vec divisors; enumerateDivisors(divisorsWithFactor[i].second, divisors); for(ll d : divisors) { if(d == divisorsWithFactor[i].first) break; ll q = divisorsWithFactor[i].first / d; // dにあってqにない素因数については自由度あり mint ziyudo = 1; for(pair p : divisorsWithFactor[divisorsToIndex[d]].second) { if(divisorsWithFactor[divisorsToIndex[q]].second.count(p.first)) continue; ziyudo *= (p.second + 1); } dp[i] += dp[divisorsToIndex[d]] * ziyudo; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N; primeEnumerate(); primeFactorizeN(); divisorsFactorize(primeFactorized.begin()); // printDivisors(); for(int i = 0; i < (int)divisorsWithFactor.size(); i++) { divisorsToIndex[divisorsWithFactor[i].first] = i; } compDP(); cout << dp.back().val() << "\n"; }