设$f[i][j]$表示考虑前$i$个人，第$i$个人在前$i$个人中排名为$j$的方案数。

对于大小关系相同的一段，转移可以看成求$k$次前/后缀和，任意一项对另一项的贡献仅和其下标差值有关，FFT加速即可。

时间复杂度$O(mn\log n)$。

 

#include
     
      #include
      
       #include
       
        using namespace std;const int N=65555,M=32768,P=1000000007;int n,m,i,j,k,t,o,len,L,R,a[30],b[N],f[N*3],ans,g[N],v[N],fin[N],fac[N],inv[N],pos[N];inline void up(int&a,int b){(a+=b)>=P&&(a-=P);}inline int C(int n,int m){return 1LL*fac[n]*inv[m]%P*inv[n-m]%P;}namespace FFT{struct comp{  long double r,i;comp(long double _r=0,long double _i=0){r=_r;i=_i;}  comp operator+(const comp&x){return comp(r+x.r,i+x.i);}  comp operator-(const comp&x){return comp(r-x.r,i-x.i);}  comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}  comp conj(){return comp(r,-i);}}A[N],B[N];int a0[N],b0[N],a1[N],b1[N];const long double pi=acos(-1.0);void FFT(comp a[],int n,int t){  for(int i=1;i
        
         
          >1]>>1|((i&1)<