Xét bài toán: Đếm số nghiệm nguyên dương ~(x, y)~ của $$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$$

Ta có: $$\frac{x + y}{xy} = \frac{1}{n}$$

Nhân chéo: $$xy = n \times (x + y)$$

Chuyển vế: $$xy - nx - ny = 0$$

Cộng ~n^2~ hai vế: $$xy - nx - ny + n^2 = n^2$$

Nhóm lại: $$(x - n)(y - n) = n^2$$

Đặt $$a = x - n, b = y - n$$

Khi đó: $$ab = n^2$$

Vì ~x, y > 0~ nên ~a > -n, b > -n~. Nhưng vì ~ab = n^2 > 0~ nên ~a, b~ cùng dấu. Nếu ~a, b~ cùng âm thì ~a \le -1, b \le -1~, nên ~x = a + n \le n - 1, y \le n - 1~, dễ dàng suy ra vô lý.

Vậy ta chỉ cần xét ~a > 0, b > 0~. Mỗi cặp ~(a, b)~ là ước của ~n~ tương ứng với một nghiệm duy nhất của bài toán qua: ~x = a + n, y = b + n~.

Vì vậy số nghiệm của bài toán này là số ước của ~n^2~.

Quay lại bài toán, ta cần đếm số lượng ước của ~(n!)^2~.

Ta phân tích ~(n!)^2~ ra thừa số nguyên tố, bằng cách phân tích ~n!~ ra thừa số nguyên tố, sau đó nhân ~2~ mọi số mũ.

Lúc đó, ta có thể tính số ước của ~(n!)^2~.

Độ phức tạp: ~O~ (~n \times log~ ~n~).

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

#define int long long
#define pp pair <int, int>
#define fi first
#define se second

const int N = 1e6 + 9;
const int mod = 20252026;

int p[N];

void sieve (){
    p[0] = p[1] = 1;
    for (int i = 2; i < N; i++) p[i] = i;
    for (int i = 2; i * i < N; i++) if (p[i] == i){
        for (int j = i * i; j < N; j += i) if (p[j] == j) p[j] = i;
    }
}

vector <pp> fact (int n){
    vector <pp> v;
    while (n > 1){
        int cnt = 0, x = p[n];
        while (n % x == 0){
            n /= x;
            cnt++;
        }
        v.push_back ({x, cnt});
    }
    return v;
}

int cnt[N];

signed main (){
    sieve ();
    int n; cin >> n;
    for (int i = 2; i <= n; i++){
        vector <pp> v = fact (i);
        for (auto [x, y] : v) cnt[x] += y * 2;
    }
    int res = 1;
    for (int i = 2; i <= n; i++) res = (res * (cnt[i] + 1)) % mod;
    cout << res << "\n";
}