Untitled

// اعداد زیبا ج
// کثیف ترین کد عمرم
//Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
void debug(int out){ cerr << out << endl; }

#define int long long
#define loop(i , l , r) for (int i = l; i <= r; i++)
#define arc(i , r , l) for (int i = r; i >= l; i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define Turbo ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sep " "
#define G pair<int,int>
#define par first
#define grand second

const int Delta = 1e4+729 , N = 1e6 , K = 250'000 , Inf = 2e18 ;
vector<int> dv(N+1);
vector<int> parent(N+1,0) , child(N+1,0);
set<int> beauty;
vector<G> S[N+1];
void get_family ()
{
    loop(i,1,N){
        for (int j = i+i; j<=N; j+=i){
            dv[j]++; child[parent[j]]--;
            parent[j] = i; child[i]++;
        } if (dv[i]>1 and dv[i]<5){ beauty.insert(i); }
    } vector<int> is_par(N+1,0);
    for (auto it : beauty){
        is_par[parent[it]]++;
    } for (auto it : beauty){
        if (is_par[it] == 0){
            int A = parent[it] , B = parent[A];
            if (beauty.count(A) == 0){ child[A] = Inf; }
            if (beauty.count(B) == 0){ child[B] = Inf; }
            G fam; fam.par = child[A]; fam.grand = child[B];
            S[child[it]].pb(fam);
        }
    } loop(i,0,N){ sort(all(S[i])); }
}

void Engine ()
{
    get_family();
    vector<int> W;
    loop(i,0,N){
        int sz = S[i].size();
        if (sz == 0){ continue; }
        loop(j,0,sz-1){
            W.pb(i);
            G v = S[i][j];
            if (v.par != Inf){
                if (v.par-1<i){ W.pb(v.par-1);
                    if (v.grand != Inf){
                        if (v.grand-1<i){ W.pb(v.grand-1); }
                        else { G q;
                            q.par = Inf; q.grand = Inf; S[v.grand-1].pb(q);
                            if (v.grand-1 != i){ sort(all(S[v.grand-1])); }
                            else { sort(S[i].begin()+j+1,S[i].end()); sz++; }
                        }
                    }
                } else { G q;
                    q.par = v.grand; q.grand = Inf; S[v.par-1].pb(q);
                    if (v.par-1 != i){ sort(all(S[v.par-1])); }
                    else { sort(S[i].begin()+j+1,S[i].end()); sz++; }
                }
            }
        }
    } int sz = W.size();
    loop(i,1,sz-1){
        W[i]+=W[i-1];
    } int out = 0 , idx = (S[0].size())-1;
    loop(i,1,K){
        while (idx+1 < W.size() and W[idx+1]<=i){ idx++; }
        int x = idx+1 , y = W[idx];
        int xy = x*y %Delta;
        out = (out + (xy*xy %Delta))%Delta;
    } cout << out << endl;
}

signed main()
{
    Turbo
    int Tc = 1; //cin >> Tc;
    clock_t start = clock();
    while (Tc--){ Engine(); }
    clock_t stop = clock();
    double elapsed = (double)(stop-start)/CLOCKS_PER_SEC;
    cout << "\nTime elapsed : " << elapsed << 's';
}