这个题目构思十分巧妙，我们考虑把这样的矩阵作为一个图的邻接矩阵，恰好满足题目中的所有条件，并且关键的一点是每一个点都有且仅有2条边。
针对这类问题可以使用dp来解决。
dp[i]表示i个点满足条件的图的种类数目。
分情况讨论可以得到状态转移方程：

dp[i]=((i-1)*dp[i-2]+(i-1)*dp[i-1]-(i-2)*(i-1)/2*dp[i-3])%m;

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
ll n,m;
ll dp[100010];
int main()
{
    while(cin>>n>>m){
    dp[1]=0;dp[2]=dp[3]=1;
        for(ll i=4;i<=n;i++) 
            dp[i]=(dp[i-1]*(i-1)+dp[i-2]*(i-1)-((i-2)*(i-1)/2)*dp[i-3])%m;
        cout<<(dp[n]+m)%m<<endl;
}
}