其实只与$n$有关,可以任意移动行,使得$i$行的障碍恰好在$i$列,那么就相当于是一个错排问题了。

$D(n)=(n-1)(D(n-1)+D(n-2))$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
#define fin(s) freopen(s".in","r",stdin)
#define I inline 
using namespace std;
const int N=1e5+5;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node
{
    int a[N];
    node(){}
    node operator *(const int w)const
    {
        node b;b.a[0]=a[0];
        for(int i=1;i<=a[0];i++)b.a[i]=a[i]*w;
        for(int i=1;i<a[0];i++)b.a[i+1]+=b.a[i]/10,b.a[i]%=10;
        while(b.a[b.a[0]]/10)b.a[b.a[0]+1]+=b.a[b.a[0]]/10,b.a[b.a[0]++]%=10;
        return b;
    }
    node operator +(const node b)const
    {
        node c;c.a[0]=max(b.a[0],a[0]);
        for(int i=1;i<=c.a[0];i++)c.a[i]=a[i]+b.a[i];
        for(int i=1;i<c.a[0];i++)c.a[i+1]+=c.a[i]/10,c.a[i]%=10;
        while(c.a[c.a[0]]/10)c.a[c.a[0]+1]+=c.a[c.a[0]]/10,c.a[c.a[0]++]%=10;
        return c;
    }
}a,b,c;
int main()
{
    int n;qr(n);
    a.a[0]=b.a[0]=1;a.a[1]=0,b.a[1]=1;
    if(n==2){puts("1");return 0;}
    for(int i=2;i<n;i++)
        c=(a+b)*i,a=b,b=c;
    for(int i=c.a[0];i>=1;i--)
        qw(c.a[i]);puts("");
    return 0;
}