Call the number of steps that a permutation takes the period of the permutation. Every permutation can be partitioned into cycles of sizes $c_1,c_2,c_3,\ldots,c_k$ such that $c_1+c_2+\ldots+c_k=N$ (see Swapity Swapity Swap from the last contest). Then the period is equal to $\text{lcm}(c_1,c_2,\ldots,c_k)$.

Suppose that we want find the minimum $n$ such that there exists a permutation of length $n$ with period $K=\prod p_i^{e_i},$ where the right side denotes the prime factorization of $K$. It turns out that $n=\sum p_i^{e_i}$ because

• It is never optimal to have $\text{gcd}(c_i,c_j)>1$ for $i\neq j$ because then we could divide each of $c_i,c_j$ by an appropriate factor. This would reduce the value of $\sum_{i=1}^kc_i$.
• It is never optimal to have $c_i=pq$ for $\min(p,q)>1$ and $\text{gcd}(p,q)=1$ because then $p+q<c_i$.

Thus, we need to find the sum of all positive integers $K$ such that $\sum p_i^{e_i}\le N$.

Subtask $N\le 100$:

Just searching for all possible $K$ suffices (there are only $18663$ for $N=100$). However, this number grows quite rapidly as $N$ increases.

Full Credit:

Maintain a DP table storing the sum of all possible $K$ for each prime power sum $n$ in $[0,N]$. Then we can add prime powers in increasing order of $p$ and update the table in $O(N)$ for each of them.

Unfortunately, I was unaware that the sequence could be found on OEIS. I'll try to be more careful about this in the future ...

Mark Chen's code:

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;

const int MAXP = 1234;
const int MAXN = 10005;
 
LL res[MAXP][MAXN];  // result for permutations of length n restricted to using the first p primes
 
int n; LL m;
 
LL mul(LL x, LL y) {
    return (x * y) % m;
}
 
LL add(LL x, LL y) {
    x += y;
    if (x >= m) x -= m;
    return x;
}
 
LL sub(LL x, LL y) {
    x -= y;
    if (x < 0) x += m;
    return x;
}
 
int main() {
    freopen("exercise.in","r",stdin);
    freopen("exercise.out","w",stdout);
    cin >> n >> m;
 
    vector<int> composite(n+1);
    vector<int> primes;
 
    for (int i = 2; i <= n; i++) {
        if (!composite[i]) {
            primes.push_back(i);
            for (int j = 2*i; j <= n; j += i) {
                composite[j] = 1;
            }
        }
    }
 
    if (primes.size() == 0) {
        cout << "1\n";
        return 0;
    }
 
    for (int j = 0; j <= n; j++) res[0][j] = 1;  // identities
 
    for (int i = 1; i <= primes.size(); i++) {
        for (int j = 0; j <= n; j++) {
            res[i][j] = res[i-1][j];
 
            int pp = primes[i-1];
            while (pp <= j) {
                res[i][j] = add(res[i][j], mul(pp, res[i-1][j-pp]));
                pp *= primes[i-1];
            }
        }
    }
 
    cout << res[primes.size()][n] << "\n";
}