打模拟赛被这个题伏击了，于是决定记录一下。
首先进行一个转化：建一个 \(n \times n\) 的网格图，对于第 \(i\) 行第 \(j\) 列的点 \((i, j)\)，和 \((i+1, j)\) 的连边上写着 \(b_j\)，和 \((i, j+1)\) 的连边上写着 \(a_i\)。从 editorial 上面偷了一个图，表示 \(a = (3, 1, 4, 2, 5), b = (3, 2, 4, 1, 5)\) 的情形。
我们要求的，就是 \((1, 1) \to (n, n)\)，只能往右走或往下走，本质不同的经过边上的数字序列个数。
我们考虑 \(f_{i, j}\) 表示 \((1, 1) \to (i, j)\) 本质不同的路径数量。如果没有本质不同的限制，那么转移就是 \(f_{i, j} = f_{i-1, j} + f_{i, j-1}\)。
但是 \(f_{i-1, j}\) 和 \(f_{i, j-1}\) 中可能有重复的。我们假设这部分中重复的方案数是 \(g_{i, j}\)。那么最后的方程是
显然 \(a_i \not = b_j\) 的时候，我们从 \((i-1, j) \to (i, j)\) 和 \((i, j-1) \to (i, j)\) 走过的边上经过的数字是不同的，所以 \(g_{i, j} = 0\)。
接下来考虑 \(a_i = b_j\) 怎么办。
我们考虑两条重复的路径是怎么样。我们枚举这两条路径最后一次相交的位置 \((p, q)\)。由于我们计算的是合并 \(\boldsymbol{f_{i-1, j}, f_{i, j-1}}\) 时多产生的重复路径数量，因此从 \((1, 1) \to (p, q)\) 的这一段是没有重复的，所以方案数就是去重后的方案数 \(f_{p, q}\)。
接下来考虑 \((p, q) \to (i, j)\) 的路径有什么性质。
我们发现，这两条路径一定会同时转向。
考虑反证。如果存在一个地方两条路径不同时转向，那么就会有两条路径在某一个时刻是平行的；由于 \(a, b\) 是 \(1 \sim n\) 的排列，所以所有平行的边上的数字互不相等。所以这两条路径不可能本质相同。
由这个观察我们进一步发现，这两条路径一定关于一条斜率为 \(1\) 的直线对称，也就是 \(i - p = j - q\)。同时由于我们钦定 \((p, q)\) 是最后一次相交的位置，所以这两条路径除了端点处，和 \((p, q), (i, j)\) 连线不交。
我们再考虑这条路径在什么时候可以转向。显然只有满足 \(a_i = b_j\) 的时候可以转向。因为要求转向后两条路径仍然相等。
我们把转向的点延长到那条直线上，与直线的交点 \((x, y)\) 一定满足 \(a_x = b_y\)，即图中五角星处。
由此每条和这条直线不交的路径都对应着一条与其本质相同的，关于这条直线对称的路径。我们只对其中一条计数，就可以计算出重复的数量 \(g_{x, y}\)。
由上图中的五角星，我们可以得到转向的最大次数。我们假设 \((p, q)\) 和 \((i, j)\) 之间有 \(t\) 个 \(a_x = b_y\) 的 \((x, y)\)（不包括 \((i, j)\)）。把转向的位置离散化一下，就变成原点走到 \((t, t)\)，不碰到 \(y = x\) 的方案数。用反射容斥或由卡特兰数定义平移一下，可以得到方案数为 \(C(t-1)\)，其中 \(C\) 是卡特兰数。
所以当 \(a_i = b_j\)，
看起来是 \(O(n^3)\) 的。但是别忘了，由于 \(a, b\) 是排列，所以 \(a_i = b_j\) 只有 \(O(n)\) 对。我们算 \(g_{i, j}\) 是 \(O(n)\) 的，所以问题在 \(O(n^2)\) 的时间内得到解决。
#include<bits/stdc++.h>
#define endl '\n'
#define N 2006
#define MOD 1000000007
using namespace std;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
inline void dec(int &x,int y) {x+=MOD-y,x-=x>=MOD?MOD:0;}
int n,a[N],b[N],fac[N],ifac[N],f[N][N];
inline int qpow(int x,int y=MOD-2)
{int ret=1;for(;y;y>>=1,x=1ll*x*x%MOD)if(y&1)ret=1ll*ret*x%MOD;return ret;
}
void init()
{fac[0]=1;for(int i=1;i<N;i++)fac[i]=1ll*i*fac[i-1]%MOD;ifac[N-1]=qpow(fac[N-1]);for(int i=N-2;~i;i--)ifac[i]=1ll*(i+1)*ifac[i+1]%MOD;
}
inline int binom(int x,int y) {return x<y?0:1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}
inline int cat(int x) {return (binom(2*x,x)-binom(2*x,x-1)+MOD)%MOD;}
main()
{scanf("%d",&n),init(),f[1][1]=1;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=1||j!=1){f[i][j]=(f[i-1][j]+f[i][j-1])%MOD;if(a[i]!=b[j])continue;for(int k=1,cnt=0;k<min(i,j);k++)if(a[i-k]==b[j-k])cnt++,dec(f[i][j],1ll*f[i-k][j-k]*cat(cnt-1)%MOD);}printf("%d\n",f[n][n]);return 0;
}