1#include <iostream>2#include <cstring>3#include <algorithm>4using namespace std;5 6const int maxn = 1000000 + 5;7const int P1 = 998244353, P2 = 1000000007;8const int B1 = 2, B2 = 31;9const int K1 = 0, K2 = 13;10 11typedef long long ll;12 13int n;14bool p[maxn];15int p1[maxn], p2[maxn];16 17struct H {18    int h1, h2, l;19    H(bool b = false) {20        h1 = b + K1;21        h2 = b + K2;22        l = 1;23    }24 25    H operator + (const H & h) const {26        H hh;27        hh.l = l + h.l;28        hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;29        hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;30        return hh;31    }32 33    bool operator == (const H & h) const {34        return l == h.l && h1 == h.h1 && h2 == h.h2;35    }36 37    bool operator < (const H & h) const {38        if (l != h.l) return l < h.l;39        else if (h1 != h.h1) return h1 < h.h1;40        else return h2 < h.h2;41    }42} h[maxn];43 44void init() {45    memset(p, 1, sizeof(p));46    p[0] = p[1] = false;47    p1[0] = p2[0] = 1;48    for (int i = 1; i <= n; ++i) {49        p1[i] = (1ll * B1 * p1[i-1]) % P1;50        p2[i] = (1ll * B2 * p2[i-1]) % P2;51        if (!p[i]) continue;52        for (int j = 2 * i; j <= n; j += i) {53            p[j] = false;54        }55    }56}57 58int solve() {59    for (int i = n; i; --i) {60        h[i] = H(p[i]);61        if (2 * i + 1 <= n) {62            h[i] = h[2 * i] + h[i] + h[2 * i + 1];63        } else if (2 * i <= n) {64            h[i] = h[2 * i] + h[i];65        }66    }67 68    cout << h[1].h1 << endl;69    sort(h + 1, h + n + 1);70    int m = unique(h + 1, h + n + 1) - (h + 1);71    return m;72}73 74int main() {75    cin >> n;76    init();77    cout << solve() << endl;78}