import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Euler844 {
    static final long kMod = 1405695061L;

    static long modAdd(long a, long b) {
        a += b;
        if (a >= kMod)
            a -= kMod;
        return a;
    }

    static long modSub(long a, long b) {
        return (a >= b) ? (a - b) : (a + kMod - b);
    }

    static long modMul(long a, long b) {
        return (a * b) % kMod;
    }

    static long modPow(long a, long e) {
        long r = 1;
        while (e > 0) {
            if ((e & 1) == 1)
                r = modMul(r, a);
            a = modMul(a, a);
            e >>= 1;
        }
        return r;
    }

    static final long inv2 = modPow(2, kMod - 2);
    static final long inv6 = modPow(6, kMod - 2);

    static long sum1Prefix(long n) {
        long a = n % kMod;
        long b = (n + 1) % kMod;
        return modMul(modMul(a, b), inv2);
    }

    static long sum2Prefix(long n) {
        long a = n % kMod;
        long b = (n + 1) % kMod;
        long c = (2 * (n % kMod) + 1) % kMod;
        return modMul(modMul(modMul(a, b), c), inv6);
    }

    static long sum3Prefix(long n) {
        long s1 = sum1Prefix(n);
        return modMul(s1, s1);
    }

    static long rangeSum1(long l, long r) {
        if (l > r)
            return 0;
        return modSub(sum1Prefix(r), sum1Prefix(l - 1));
    }

    static long rangeSum2(long l, long r) {
        if (l > r)
            return 0;
        return modSub(sum2Prefix(r), sum2Prefix(l - 1));
    }

    static long rangeSum3(long l, long r) {
        if (l > r)
            return 0;
        return modSub(sum3Prefix(r), sum3Prefix(l - 1));
    }

    static long maxKU2(long n) {
        long lo = 0, hi = 2000000000L;
        while (lo < hi) {
            long mid = lo + (hi - lo + 1) / 2;
            long val = mid * mid - mid - 1;
            if (val <= n)
                lo = mid;
            else
                hi = mid - 1;
        }
        return lo;
    }

    static java.math.BigInteger toBI(long v) {
        return java.math.BigInteger.valueOf(v);
    }

    static long maxKU3(long n) {
        long lo = 0, hi = 2000000L;
        java.math.BigInteger nBi = toBI(n);
        while (lo < hi) {
            long mid = lo + (hi - lo + 1) / 2;
            java.math.BigInteger mBi = toBI(mid);
            java.math.BigInteger val = mBi.pow(3).subtract(mBi.pow(2)).subtract(toBI(2).multiply(mBi))
                    .add(java.math.BigInteger.ONE);
            if (val.compareTo(nBi) <= 0)
                lo = mid;
            else
                hi = mid - 1;
        }
        return lo;
    }

    static long maxKSeed4(long n) {
        long lo = 0, hi = 2000000L;
        java.math.BigInteger nBi = toBI(n);
        while (lo < hi) {
            long mid = lo + (hi - lo + 1) / 2;
            java.math.BigInteger mBi = toBI(mid);
            java.math.BigInteger val = mBi.multiply(mBi.subtract(java.math.BigInteger.ONE))
                    .multiply(mBi.pow(2).subtract(mBi).subtract(java.math.BigInteger.ONE))
                    .subtract(java.math.BigInteger.ONE);
            if (val.compareTo(nBi) <= 0)
                lo = mid;
            else
                hi = mid - 1;
        }
        return lo;
    }

    static boolean cappedProductExcept(ArrayList<Long> v, int skip, long cap, long[] out) {
        java.math.BigInteger prod = java.math.BigInteger.ONE;
        java.math.BigInteger capBi = toBI(cap);
        for (int i = 0; i < v.size(); ++i) {
            if (i == skip)
                continue;
            if (prod.compareTo(capBi.divide(toBI(v.get(i)))) > 0)
                return false;
            prod = prod.multiply(toBI(v.get(i)));
        }
        out[0] = prod.longValue();
        return true;
    }

    static long exactMK(long k, long n) {
        Queue<ArrayList<Long>> q = new LinkedList<>();
        HashSet<ArrayList<Long>> seen = new HashSet<>();
        HashSet<Long> numbers = new HashSet<>();

        ArrayList<Long> start = new ArrayList<>();
        q.add(start);
        seen.add(start);
        numbers.add(1L);

        while (!q.isEmpty()) {
            ArrayList<Long> cur = q.poll();

            for (long x : cur) {
                if (x <= n)
                    numbers.add(x);
            }

            long ones = k - cur.size();

            if (ones > 0) {
                long cap = (n + 1) / k;
                long[] prodArr = new long[1];
                if (cappedProductExcept(cur, -1, cap, prodArr)) {
                    long prod = prodArr[0];
                    long y = k * prod - 1;
                    if (y <= n) {
                        ArrayList<Long> nxt = new ArrayList<>(cur);
                        int pos = Collections.binarySearch(nxt, y);
                        if (pos < 0)
                            pos = -(pos + 1);
                        nxt.add(pos, y);
                        if (seen.add(nxt))
                            q.add(nxt);
                    }
                }
            }

            for (int i = 0; i < cur.size(); ++i) {
                if (i > 0 && cur.get(i).equals(cur.get(i - 1)))
                    continue;
                long x = cur.get(i);
                long cap = (n + x) / k;
                long[] prodArr = new long[1];
                if (!cappedProductExcept(cur, i, cap, prodArr))
                    continue;
                long prodOthers = prodArr[0];

                long y = k * prodOthers - x;
                if (y == 0)
                    continue;

                ArrayList<Long> nxt = new ArrayList<>(cur);
                nxt.remove(i);
                if (y > 1) {
                    int pos = Collections.binarySearch(nxt, y);
                    if (pos < 0)
                        pos = -(pos + 1);
                    nxt.add(pos, y);
                }
                if (!nxt.isEmpty() && nxt.get(nxt.size() - 1) > n)
                    continue;
                if (seen.add(nxt))
                    q.add(nxt);
            }
        }

        long out = 0;
        for (long x : numbers)
            out = modAdd(out, x % kMod);
        return out;
    }

    static long chainSumRange(long l, long r, long n, long k2max, long k3max) {
        if (l > r)
            return 0;

        long ans = rangeSum1(l, r);

        if (l <= k2max) {
            long rr = Math.min(r, k2max);
            long cnt = (rr - l + 1) % kMod;
            long s2 = rangeSum2(l, rr);
            long s1 = rangeSum1(l, rr);
            long add = modSub(modSub(s2, s1), cnt);
            ans = modAdd(ans, add);
        }

        if (l <= k3max) {
            long rr = Math.min(r, k3max);
            long cnt = (rr - l + 1) % kMod;
            long s3 = rangeSum3(l, rr);
            long s2 = rangeSum2(l, rr);
            long s1 = rangeSum1(l, rr);
            long add = modSub(modSub(s3, s2), modMul(2, s1));
            add = modAdd(add, cnt);
            ans = modAdd(ans, add);
        }

        return ans;
    }

    static long solveBig(long K, long N) {
        if (K < 3)
            return 0;

        long k2max = maxKU2(N);
        long k3max = maxKU3(N);
        long k0 = maxKSeed4(N);

        long exactTo = Math.min(K, k0);
        long ans = 0;
        for (long k = 3; k <= exactTo; ++k) {
            ans = modAdd(ans, exactMK(k, N));
        }

        if (K > exactTo) {
            long l = Math.max(3L, exactTo + 1);
            ans = modAdd(ans, chainSumRange(l, K, N, k2max, k3max));
        }

        return ans;
    }

    public static String solve() {
        return Long.toString(solveBig(1000000000000000000L, 1000000000000000000L));
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}