Untitled

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M = 1e6 + 500;
const ll dlt = 10739;
ll nchildren[M];
ll inf = 1e6 - 1;
set <int> beauty;
bool mark[M] = {};
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)]++;
    }
}
ll i_wana_be_a_spy(ll n){
    ll ans = (1e12) * nchildren[n];
    ll 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;
}
void make(int n){
    for(int i = 2; i <= n; i++){
        if(num_divisors(i) >= 3 and num_divisors(i) <= 5)
            beauty.insert(i);
    }
    for(auto u : beauty){
        mark[father(u)] = 1;
    }
}
int main(){
    ios::sync_with_stdio(0); //cin.tie(0);
    ll n, k;
    cin >> n >> k;
    multiset <ll> vec;
    num_children(n);
    make(n);
    cout << beauty.size() << endl;
    for(auto u : beauty){
        if(!mark[u])
            vec.insert(i_wana_be_a_spy(u));
    }
    ll sum = 0;
    ll x = 0, y = 0, help = 0;
    cout << vec.size() << endl;
    while(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 << x << endl;
    cout << vec.size() << endl;
    for(int i = 1; i <= k; i++){
        if(!vec.empty()){
            ll neww = *vec.begin();
            neww -= 1e12;
            vec.erase(vec.begin());
            vec.insert(neww);
            help++;
            while(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;
}