分析
观察样例容易发现，本题的序列其实是很多个环的结合。不同的环按照特定的周期循环，在这些周期的公倍数时会恢复为原数列。
更加严谨的表述是：给定序列(1sim n)，记为(p)。求(lcm(|S_i|))，其中(S_i)满足(S_icup S_j=emptyset)，且(S_1cap S_2 cap ... cap S_k=p)，并且有(forall jin S_i, p_jin S_i)。
那么本题的问题就转化为了求(N)的拆分的最小公倍数。又因为最小公倍数只被各个素因数最高次幂决定，所以说就等价于求(1sim N)的素数分解。
设子状态(f_{i,j})表示素数总和为(i)最大的素数为(p_j)的情况的答案。不难想到状态转移方程(f_{i,j}=f_{i,j-1}+sum f_{i-{p_j}^k,j-1}*{p_j}^k)。
(N)的上限为1e4，随便什么筛筛一下素数就可以了。
代码
/*
By Nero Claudius Caeser Augustus Germanicus,
Imperatorum Romanorum.
*/
#include <bits/stdc++.h>
using namespace std;
namespace StandardIO{
template<typename T>void read(T &x){
x=0;T f=1;char c=getchar();
for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=-1;
for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
x*=f;
}
template<typename T>void write(T x){
if(x<0) putchar('-'),x*=-1;
if(x>=10) write(x/10);
putchar(x%10+'0');
}
} using namespace StandardIO;
namespace Project{
#define int long long
const int N=10000+10;
int n,m,ans;
int vis[N];
int prime[N];
int f[N][N/2];
void MAIN(){
read(n),read(m);
for(int i=2; i<=n; ++i){
if(!vis[i]){
prime[++prime[0]]=i;
for(int j=i*2; j<=n; j+=i) vis[j]=1;
}
}
for(int i=0; i<=prime[0]; ++i) f[0][i]=1;
for(int i=1; i<=n; ++i){
for(int j=1; j<=prime[0]; ++j){
f[i][j]=f[i][j-1];
for(int k=prime[j]; k<=i; k*=prime[j]){
(f[i][j]+=(f[i-k][j-1]*k)%m)%=m;
}
}
}
for(int i=0; i<=n; ++i){
(ans+=f[i][prime[0]])%=m;
}
write(ans%m);
}
#undef int
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
Project::MAIN();
}