A1580 学术精神

// A1580 学术精神 —— 期望的边数与连通块数
//
// 模型：每个点 i 反复抽卡片，直到抽到别的点 j（j != i）为止；
//       抽到自己的那些「自环」边也保留，所以总边数 = 总抽卡次数。
//       每个点恰好产生一条连向别人的边，于是得到一张「随机函数图」。
//
// E0（总抽卡次数的期望）：
//   一次抽卡成功的概率 p = (n-1)/n，故每人的抽卡次数服从几何分布，
//   期望为 1/p = n/(n-1)，n 个人共 n^2/(n-1)。
//
// E1（连通块个数的期望）：
//   随机函数图的每个连通块恰好含一个环，所以连通块数 = 环的个数。
//   长度为 k (k >= 2) 的环：先选 k 个点 C(n,k)，把它们排成环有 (k-1)! 种，
//   每个点连向环上的下一个点，概率 (1/(n-1))^k。
//   E1 = sum_{k=2}^{n} C(n,k) * (k-1)! * (n-1)^{-k}。
//   （k = 1 的自环已被抽卡规则排除。）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 998244353;
const int MAXN = 100000 + 5;

ll fac[MAXN], ifac[MAXN];

ll qpow(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[n] = qpow(fac[n], MOD - 2);
    for (int i = n; i >= 1; i--) ifac[i - 1] = ifac[i] * i % MOD;

    ll inv = qpow(n - 1, MOD - 2); // (n-1) 的逆元

    // E0 = n^2 / (n-1)
    ll e0 = (ll)n * n % MOD * inv % MOD;

    // E1 = sum_{k=2}^{n} C(n,k) * (k-1)! * inv^k
    ll e1 = 0;
    ll pw = inv * inv % MOD; // inv^2
    for (int k = 2; k <= n; k++) {
        ll c = fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
        ll term = c * fac[k - 1] % MOD * pw % MOD;
        e1 = (e1 + term) % MOD;
        pw = pw * inv % MOD;
    }

    cout << e0 << '\n' << e1 << '\n';
    return 0;
}