t4

constexpr int MAXN = 1e5 + 3;
class Solution {
    // using ll = long long;
    using ll = int;
    const static int MOD = 1000 * 1000 * 1000 + 7;

    vector<int> not_prime;
    vector<int> pf;
    vector<int> pfcnt;
    vector<int> pri;
    int cnt = 0;
    void init() {
      not_prime = vector<int>(MAXN);
      pf = vector<int>(MAXN);
      pfcnt = vector<int>(MAXN);
      pri = vector<int>(MAXN);
      pf[1] = 1;
      for (int i = 2; i < MAXN; ++i) {
        if (!not_prime[i]) {
          pri[cnt++] = i;
          pf[i] = i;
          pfcnt[i] = 1;
        }
        for (int j = 0; j < cnt; ++j) {
          if (1ll * i * pri[j] >= MAXN) break;
          not_prime[i * pri[j]] = 1;
          pf[i * pri[j]] = pri[j];
          pfcnt[i * pri[j]] = pfcnt[pri[j]] + 1;
          if (i % pri[j] == 0) {
            break;
          }
        }
      }
    }

    vector<vector<ll>> dp;

    vector<int> fs;
    vector<int> fcnt;

    map<int, int> fmap;

    void factorize(int n) {
        fmap.clear();
        while(n != 1) {
            fmap[pf[n]] += 1;
            n = n / pf[n];
        }
    }

    vector<vector<int>> comb;
    void get_c(int n, int k) {
        comb = vector<vector<int>>(n + k, vector<int>(k, 0));
        comb[0][0] = 1;
        comb[1][0] = comb[1][1] = 1;
        for (int i = 2; i < n + k; ++i) {
            comb[i][0] = 1;
            // comb[i][i] = 1;
            for (int j = 1; j < k; ++j) {
                comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
            }
        }
    }

    void dfs(const vector<pair<int, int>>& fs, int beg, int acc, unordered_set<int>& s, int& dnum, int n, int v) {
        if (beg == fs.size()) {
            return;
        }
        for (int i = 0; i < fs[beg].second; ++i) {
            if (s.count(acc) == 0) {
                s.insert(acc);
                dnum = (dnum + search(n - 1, acc)) % MOD;
            }
            if (s.count(v / acc) == 0) {
                s.insert(v/ acc);
                dnum = (dnum + search(n - 1, v/ acc)) % MOD;
            }
            dfs(fs, beg + 1, acc, s, dnum, n, v);
            acc = acc * fs[beg].first;
            dfs(fs, beg + 1, acc, s, dnum, n, v);
        }
    }
    int search(int n, int v) {
        int oldv = v;
        if (dp[n][v] != -1) {
            return dp[n][v];
        }

        int& rs = dp[n][v];
        int acc = 1;
        while(v != 1) {
            int k = pfcnt[v];
            for (int i = 0; i < k; ++i) v = v / pf[v];
            acc = (acc * comb[n + k][k] % MOD) % MOD;
        }
        rs = acc;
        // unordered_set<int> vs;
        // vs.insert(v);
        // dp[n][v] = search(n - 1, v);
        /*
        for (int i = 2; i <= v; ++i) {
            if (v % i == 0) {
                dp[n][oldv] = (dp[n][oldv] + search(n - 1, v / i)) % MOD;
            }
        }
        */

        // factorize(v);
        // vector<pair<int, int>> fs(fmap.begin(), fmap.end());
        // dfs(fs, 0, 1, vs, dp[n][oldv], n, v);
        /*
        while (v != 1) {
            if (vs.count(v/pf[v]) == 0) {
                vs.insert(v/pf[v]);
                dp[n][oldv] = (dp[n][oldv] + search(n - 1, v / pf[v])) % MOD;
            }
            if (vs.count(pf[v]) == 0) {
                dp[n][oldv] = (dp[n][oldv] + search(n - 1, pf[v])) % MOD;
                vs.insert(pf[v]);
            }

            v = v / pf[v];
        }

        if (vs.count(1) == 0)
            dp[n][oldv] = (dp[n][oldv] + search(n - 1, 1)) % MOD;
        */

        // printf("dp[%d][%d]: %d\n", n, oldv, dp[n][oldv]);
        return dp[n][oldv];
    }

public:
    int idealArrays(int n, int maxValue) {
        dp = vector<vector<ll>>(n, vector<ll>(maxValue + 1, -1));
        dp[0] = vector<ll>(maxValue + 1, 1);
        ll ans = 0;
        init();
        int k = 14; // log(1e4) ~= 13
        get_c(n, k);
        // cout << "get c" << endl;
        for (int i = maxValue; i > 0; --i) {
            ans = (ans + search(n - 1, i)) % MOD;
        }
        return ans;
    }
};