Untitled

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M = 1e6 + 500;
const ll dlt = 10289;
ll nchildren[M];
ll inf = 1e6 - 1;
ll mod(ll n){
    n = n % dlt;
    if(n < 0)
        n += dlt;
    return n;
}
ll father(ll a){
    for(ll i = 2; i * i <= a; i++)
        if(!(a % i))
            return a / i;
    return 1;
}
ll num_divisors(int a){
    int ans = 1;
    for(int i = 2; i*i <= a; i++){
        int cnt = 0;
        while(!(a % i)){
            a /= i;
            cnt ++;
        }
        ans *= (cnt + 1);
    }
    if(a != 1)
        ans *= 2;
    return ans;
}
void num_children(int n){
    for(int i = 2; i <= n; i++){
        nchildren[father(i)]++;
    }
}

bool check(ll n, ll a){
    vector <ll> vec;
    for(int i = 2; i * i <= a; i++){
        ll b = a / i;
        if(!(a % i)){
            if(!vec.empty()){
                if(i % vec.back())
                    vec.push_back(i);
            }
            else
                vec.push_back(i);
        }
        //// b :
        if(!(a % b)){
            if(!vec.empty()){
                if(b % vec.back())
                    vec.push_back(b);
            }
            else
                vec.push_back(b);
        }
    }
    if(vec.size() > 1)
        return 1;
    ll x = 1;
    while(x < a)
        x *= vec[0];
    x *= vec[0];
    if(x > n)
        return 1;
    return 0;
}
ll i_wana_be_a_spy(ll n){
    ll ans = (1e12) * nchildren[n];
    int u = father(n);
    if(num_divisors(u) >= 3 and num_divisors(u) <= 5)
        ans += (1e6) * nchildren[u];
    else
        ans += (1e6) * inf;
    u = father(u);
    if(num_divisors(u) >= 3 and num_divisors(u) <= 5)
        ans += nchildren[u];
    else
        ans += inf;

    return ans;
}
ll who_am_i(ll n){
    const ll a = 1e12;
    return n / a;
}
ll who_is_myfather(ll n){
    ll a = 1e12;
    n = n % a;
    a = 1e6;
    n /= a;
    return n;
}
ll who_is_mygrandfather(ll n){
    ll a = 1e6;
    return n % a;
}

int main(){
    ios::sync_with_stdio(0); //cin.tie(0);
    ll n, k;
    cin >> n >> k;
    multiset <ll> vec;
    num_children(n);
    for(ll i = 2; i <= n; i++){
        if(num_divisors(i) == 3 or num_divisors(i) == 4  or num_divisors(i) == 5){
            if(check(n, i)){
                vec.insert(i_wana_be_a_spy(i));
            }
        }
    }
    cout << "buge1" << endl;
    ll sum = 0;
    ll x = 0, y = 0, help = 0;
    while(!vec.empty() and who_am_i(*vec.begin()) == 0){
        x++;
        ll u = who_is_myfather(*vec.begin());
        ll v = who_is_mygrandfather(*vec.begin());
        vec.erase(vec.begin());
        if(u != inf)
            vec.insert((u - 1) * 1e12 + v * 1e6 + inf);
    }
    cout << vec.size() << endl;
    for(int i = 1; i <= k; i++){
        if(!vec.empty()){
            ll neww = *vec.begin() - 1e12;
            vec.erase(vec.begin());
            vec.insert(neww);
            help ++;
            if(who_am_i(*vec.begin()) == 0){
                x++;
                y += help;
                help = 0;
                ll u = who_is_myfather(*vec.begin());
                ll v = who_is_mygrandfather(*vec.begin());
                vec.erase(vec.begin());
                if(u != inf)
                    vec.insert((u - 1) * (1e12) + v * (1e6) + inf);
            }
        }
        ll A = mod(x * y);
        sum = mod(sum + mod(A * A));
    }
    cout << sum << endl;
    return 0;
}