C. inequalities

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define mp make_pair
#define pb push_back

constexpr int N = (int)2e5 + 111;
constexpr int md = (int)1050000011;
constexpr int inv6 = 175000002;

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")

map<int,int> s[66];
long long n,m;
vector<int> cur;

int bpow(int a,int b){
    if(b == 0) return 1;
    if(b % 2 == 0){
        int t = bpow(a,b>>1);
        return 1ll * t * t % md;
    }
    return (1ll * a * bpow(a,b-1)) % md;
}

__int128 bpow2(int a,int b){
    if(b == 0) return 1;
    if(b % 2 == 0){
        __int128 t = bpow2(a,b>>1);
        return t * t;
    }
    return (a * bpow2(a,b-1));
}

void add(int& a,int b){
    a = (a + b >= md ? a + b - md : a + b);
}

int sum(long long l,long long r){
    l--;
    int a = 1ll * r * (r + 1) % md * (2 * r + 1) % md * inv6 % md;
    int b = 1ll * l * (l + 1) % md * (2 * l + 1) % md * inv6 % md;
    a = (a - b < 0 ? a - b + md : a - b);
    return a;
}

int f3(int x){
    long long l = sqrtl(1ll * x*x*x);
    if(l * l < 1ll * x * x * x)
        l++;
    long long r = sqrtl(m);
//        cerr << i << " " << x << ": " << ((r - l + 1) * ((m+1) % md) % md - sum(l,r) + md) % md << "\n";
    return max(0ll,1ll*(r - l + 1) * ((m+1) % md) % md - sum(l,r) + md) % md;
}

int dp[8][(int)1e6+10];
int suff[8][(int)1e6+10];
int dp2[11][(int)1e3+10];
int suff2[11][(int)1e3+10];

int get(int i,int x){
    if(i == 1){
        return 1;
    }
    if(x != 0 && i == 2){
        return max(0ll,m-1ll*x*x+1) % md;
    }
    if(x != 0 && i == 3){
        return f3(x);
    }
    if(x != 0 && i == 4){
        return dp[4][x];
    }
    if(x != 0 && i == 5){
        return dp[5][x];
    }
    if(x != 0 && i == 6)
        return dp[6][x];
    if(x != 0 && i == 7)
        return dp[7][x];
    if(x != 0 && i <= 10)
        return dp2[i][x];
    if(s[i].count(x))
        return s[i][x];
    int ans = 0;
    long long t = pow(m,1.0/(i-1));
    for(int j = 1; j <= min(m,t); j++){
        __int128 c = 1, c2 = x;
        for(int p = 0; p < i-1; p++){
            c *= j;
            c2 *= x;
        }
        if(c < c2 || c > m)
            continue;
//        cur.pb(j);
        add(ans,get(i-1,j));
//        cur.pop_back();
    }
    return s[i][x] = ans;
}

void solve(){
    cin >> n >> m;

    n = min(n,__lg(m));

    if(n == 1){
        cout << m%md << "\n";
        return;
    }

    for(int i = cbrtl(m); i > 0; i--){
        suff[3][i] = suff[3][i+1];
        add(suff[3][i],f3(i));
    }
//    cerr << "3\n";
//    cerr << "m^1/4: " << pow(m,1.0/4) << "\n";

    __int128 r;
    r = pow(m,1.0/3);
    for(__int128 i = pow(m,1.0/4); i > 0; i--){
        while(r * r * r >= i * i * i * i)
            r--;
        dp[4][i] = suff[3][r+1];
        suff[4][i] = suff[4][i+1];
        add(suff[4][i],dp[4][i]);
    }
//    cerr << "4\n";

    r = pow(m,1.0/4);
    for(__int128 i = pow(m,1.0/5); i > 0; i--){
        while(r * r * r * r >= i * i * i * i * i)
            r--;
        dp[5][i] = suff[4][r+1];
        suff[5][i] = suff[5][i+1];
        add(suff[5][i],dp[5][i]);
    }
//    cerr << "5\n";

    r = pow(m,1.0/5);
    for(__int128 i = pow(m,1.0/6); i > 0; i--){
        while(r * r * r * r * r >= i * i * i * i * i * i)
            r--;
        dp[6][i] = suff[5][r+1];
        suff[6][i] = suff[6][i+1];
        add(suff[6][i],dp[6][i]);
    }
//    cerr << "6\n";

    r = pow(m,1.0/6);
    for(__int128 i = pow(m,1.0/7); i > 0; i--){
        while(r * r * r * r * r * r >= i * i * i * i * i * i * i)
            r--;
        dp[7][i] = suff[6][r+1];
        suff[7][i] = suff[7][i+1];
        add(suff[7][i],dp[7][i]);
    }

    r = pow(m,1.0/7);
    for(__int128 i = pow(m,1.0/8); i > 0; i--){
        while(r * r * r * r * r * r * r >= i * i * i * i * i * i * i * i)
            r--;
        dp2[8][i] = suff[7][r+1];
        suff2[8][i] = suff2[8][i+1];
        add(suff2[8][i],dp2[8][i]);
    }

    r = pow(m,1.0/8);
    for(__int128 i = pow(m,1.0/9); i > 0; i--){
        while(r * r * r * r * r * r * r * r >= i * i * i * i * i * i * i * i * i)
            r--;
        dp2[9][i] = suff2[8][r+1];
        suff2[9][i] = suff2[9][i+1];
        add(suff2[9][i],dp2[9][i]);
    }

    r = pow(m,1.0/9);
    for(__int128 i = pow(m,1.0/10); i > 0; i--){
        while(r * r * r * r * r * r * r * r * r >= i * i * i * i * i * i * i * i * i * i)
            r--;
        dp2[10][i] = suff2[9][r+1];
        suff2[10][i] = suff2[10][i+1];
        add(suff2[10][i],dp2[10][i]);
    }

    cout << get(n+1,1) << "\n";

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
//  freopen("output.txt","w",stdout);
    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
        solve();
    }
    return 0;
}
/**
a_i^i <= a_{i-1} ^ {i-1}
a_i^i * a_{i-1} <= a_{i-1}^i

i * log(a_i) <= (i-1) * log(a_{i-1})

i/(i-1) * log(a_i) <= log(a_{i-1})

a_{i-1} >= exp(i/(i-1)*log(a_i))

2 1
1 1

9 1
9 2
9 3


**/