Cod sursă (job #786481)

#include <bits/stdc++.h>
using namespace std;
ifstream fin ("dejavu.in");
ofstream fout ("dejavu.out");

#define int long long

const int MAXN=1e3+10;
const int MOD=1e9+7;

int dp[MAXN][MAXN],aib[2][MAXN];
int n,q;

void update (bool nr, int pos, int val){
    for (int i=pos;i<=n;i+=(i&(-i)))
        aib[nr][i]+=val;
}
int query (bool nr, int pos){
    int rez=0;
    for (int i=pos;i>=1;i-=(i&(-i)))
        rez+=aib[nr][i];
    return rez;
}

void init (){
    for (int i=0;i<MAXN;++i){
        for (int j=0;j<MAXN;++j){
            dp[i][j]=-1;
        }
    }
}

void prec (int i, int j){

    if (dp[i][j]!=-1) return;

    if (j>i/2){
        dp[i][j]=0;
        return;
    }
    if (i==n){
        dp[i][j]=1;
        return;
    }

    prec (i+1,j+1);
    prec (i+1,j);

    dp[i][j]=(dp[i+1][j+1]*(i-2*j)%MOD+dp[i+1][j]*(n-i+j)%MOD)%MOD;
}

void solve (){

    for (int i=1;i<=q;++i){
        for (int j=1;j<=n;++j){
            update (0,j,-(query (0,j)-query (0,j-1))+1);
            update (1,j,-(query (1,j)-query (1,j-1)));
            //aib[1][j]=0;
        }
        int rez=0,nr2=0;
        for (int j=1;j<=n;++j){
            int x;
            fin >>x;
            int nr0=query (0,x-1),nr1=query (1,x-1);

            rez=(rez+(dp[j][nr2]*nr0%MOD+dp[j][nr2+1]*nr1%MOD)%MOD)%MOD;

            if (query (0,x)-query (0,x-1)==1){
                update (0,x,-1);
                update (1,x,1);
            }
            else{
                if (query (1,x)-query (1,x-1)==1){
                    update (1,x,-1);
                    nr2++;
                }
            }

        }
        fout <<rez<<'\n';
    }
}

signed main()
{
    fin >>n>>q;

    init ();
    prec (0,0);

    /*for (int i=0;i<=n;++i){
        for (int j=0;j<=i/2;++j){
            fout <<dp[i][j]<<' ';
        }
        fout <<'\n';
    }*/
    solve ();
    return 0;
}