#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>

#define rint register int
#define I inline

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

template<class T> inline void read(T &x){
    x=0;char c=getchar();int f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();} x*=f;
}

const int N=210;
int n,p;
int C[N][N];
int f[N],g[N][N];

I int add(int a,int b){return a+b>=p?a+b-p:a+b;}
I void Add(int &a,int b){a=add(a,b);}
I int mul(int a,int b){return 1ll*a*b>=p?1ll*a*b%p:a*b;}
I void Mul(int &a,int b){a=mul(a,b);}
I int ksm(int a,int b){int t=1%p;for(;b;b>>=1){if(b&1)Mul(t,a);Mul(a,a);}return t;}

I void Prework(){
    for(rint i=0;i<=n;i++)
        for(rint j=0;j<=i;j++){
            if(!j||j==i) C[i][j]=1;
            else C[i][j]=add(C[i-1][j],C[i-1][j-1]);
        }   

    int res=3; f[1]=1;
    for(rint i=3;i<=n;Mul(res,++i)) f[i]=res;
    g[0][0]=1;
    for(rint i=1;i<=n;i++)
        for(rint j=1;j<=i;j++)
            for(rint k=1;k<=i-j+1;k++)
                Add(g[i][j],mul(mul(g[i-k][j-1],C[i-1][k-1]),f[k]));
}

int main(){
    read(n),read(p);
    Prework();  
    int ans=f[n-1],tmp=1;
    for(rint i=2;i<=n;i++,Mul(tmp,n)) 
        Add(ans,mul(tmp,g[n][i]));
    printf("%d\n",ans);
    return 0;
}

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>

#define rint register int
#define il inline

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

template<class T> inline void read(T &x){
    x=0;char c=getchar();int f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();} x*=f;
}

const int N=210,M=21000;
const int INF=1e9;

int n,m,S,T;
int h[N],e[M],ne[M],f[M],idx;
int cur[N],q[N],d[N],t[N],lc[M];

il void Add(int a,int b,int c){
    e[++idx]=b,ne[idx]=h[a],h[a]=idx,f[idx]=c;
    e[++idx]=a,ne[idx]=h[b],h[b]=idx,f[idx]=0;
}

bool Bfs(){
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    d[S]=0,q[0]=S,cur[S]=h[S];
    while(hh<=tt){
        int u=q[hh++];
        for(int i=h[u];i;i=ne[i]){
            int y=e[i];
            if(d[y]==-1&&f[i]){
                cur[y]=h[y];
                d[y]=d[u]+1;
                if(y==T) return 1;
                q[++tt]=y;
            }
        }
    }
    return 0;
}

int Dinic(int u,int limit){
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int y=e[i];
        if(d[y]==d[u]+1&&f[i]){
            int res=Dinic(y,std::min(limit-flow,f[i]));
            if(!res) d[y]=-1;
            f[i]-=res,f[i^1]+=res,flow+=res;
        }
    }
    return flow;
}

int main(){
    read(n);read(m);
    S=0,T=n+1,idx=1;
    for(int i=1;i<=m;i++){
        int a,b,c,d;
        read(a),read(b),read(c),read(d);
        Add(a,b,d-c);
        t[a]-=c,t[b]+=c; lc[i]=c;
    }
    int tot=0;
    for(int i=1;i<=n;i++) 
        if(t[i]>0) Add(S,i,t[i]),tot+=t[i];
        else if(t[i]<0) Add(i,T,-t[i]);

    int Mf=0,flow;
    while(Bfs()) while(flow=Dinic(S,INF)) Mf+=flow;
    if(Mf!=tot) puts("NO");
    else{
        puts("YES");
        for(int i=2,j=1;j<=m;j++,i+=2) 
            printf("%d\n",f[i^1]+lc[j]);
    } 
    return 0;
} 

边数至少为 $(150\times 270+150+270)\times 2$
因为边开少调了半天..

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>

#define il inline

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

template<class T> inline void read(T &x){
    x=0;char c=getchar();int f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();} x*=f;
}

const int N=500;
const int M=100000;
const int INF=1e8;

int n,m,S,T,sum;
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N],q[N];

il void Add(int a,int b,int c){
  //printf("%d %d %d\n",a,b,c);
  e[++idx]=b,ne[idx]=h[a],h[a]=idx,f[idx]=c;
  e[++idx]=a,ne[idx]=h[b],h[b]=idx,f[idx]=0;
}

bool Bfs(){
  int hh=0,tt=0;
  memset(d,-1,sizeof d);
  d[S]=0; q[0]=S; cur[S]=h[S];
  while(hh<=tt){
    int u=q[hh++];
    for(int i=h[u];i;i=ne[i]){
      int y=e[i];
      if(d[y]==-1&&f[i]){
        d[y]=d[u]+1;
        cur[y]=h[y];
        if(y==T) return 1;
        q[++tt]=y;
      }
    }
  }
  return 0;
}

int Dinic(int u,int limit){
  if(u==T) return limit;
  int flow=0;
  for(int i=cur[u];i&&flow<limit;i=ne[i]){
    int y=e[i];
    cur[u]=i;
    if(f[i]&&d[y]==d[u]+1){
      int t=Dinic(y,std::min(limit-flow,f[i]));
      if(!t) d[y]=-1;
      f[i]-=t,f[i^1]+=t,flow+=t;
    }
  }
  return flow;
}

int main(){
  read(m);read(n);
  S=0,T=n+m+1,idx=1;
  for(int i=1,x;i<=m;i++) read(x),sum+=x,Add(S,i,x);
  for(int i=1,x;i<=n;i++) read(x),Add(i+m,T,x);
  for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++) 
      Add(i,j+m,1);

  int MF=0,flow; 
  while(Bfs()) while(flow=Dinic(S,INF)) MF+=flow;
    if(MF<sum) puts("0");
    else{
        puts("1");
        std::vector<int> ver[N];
        for(int i=2;i<idx;i+=2)
          if(e[i]>m&&e[i]<=n+m&&!f[i])
            ver[e[i^1]].push_back(e[i]);
        for(int i=1;i<=m;i++,puts(""))
        for(int j=0;j<ver[i].size();j++)
            printf("%d ",ver[i][j]-m);
    }
  return 0;
}

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>

#define rint register int
#define il inline

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

template<class T> inline void read(T &x){
    x=0;char c=getchar();int f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();} x*=f;
}

const int N=100010;

int n,m;
int h[N],e[N<<1],ne[N<<1],idx;
int id[N],siz[N],son[N],fa[N],dep[N],top[N],tot;
struct SGT{
    int l,r,s,lz;
    void init(int _l,int _r){
        l=_l; r=_r; lz=s=0;
    }
}tr[N<<2];

il void Add(int a,int b){ e[++idx]=b,ne[idx]=h[a],h[a]=idx; }
void Dfs1(int u,int father){
    fa[u]=father,dep[u]=dep[father]+1,siz[u]=1;
    for(rint i=h[u];i;i=ne[i]){
        int y=e[i];
        if(y==father) continue;
        Dfs1(y,u);
        siz[u]+=siz[y];
        if(siz[son[u]]<siz[y]) son[u]=y; 
    }   
}

void Dfs2(int u,int f){
    id[u]=++tot;
    top[u]=f;
    if(!son[u]) return;
    Dfs2(son[u],f);
    for(rint i=h[u];i;i=ne[i]){
        int y=e[i];
        if(y==fa[u]||y==son[u]) continue;
        Dfs2(y,y);
    }
}

#define ls p<<1
#define rs p<<1|1
il void Pushup(int p){ tr[p].s=tr[ls].s+tr[rs].s; }
il void Pushdown(int p){
    if(tr[p].lz==0) return;
    if(tr[p].lz==1){
        tr[ls].s=tr[ls].r-tr[ls].l+1, tr[ls].lz=1;
        tr[rs].s=tr[rs].r-tr[rs].l+1, tr[rs].lz=1;
    }else{
        tr[ls].s=0, tr[ls].lz=-1;
        tr[rs].s=0, tr[rs].lz=-1;
    } tr[p].lz=0;
}

void Build(int p,int l,int r){
    tr[p].init(l,r);
    if(l==r) return;
    int mid=l+r>>1;
    Build(ls,l,mid), Build(rs,mid+1,r);
}
void Modify(int p,int l,int r,int k){
    if(l<=tr[p].l&&tr[p].r<=r){
        if(k==1) {
            tr[p].s=tr[p].r-tr[p].l+1;
            tr[p].lz=1;
        } else{
            tr[p].s=0, tr[p].lz=-1;
        }
        return;
    }
    Pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if(l<=mid) Modify(ls,l,r,k);
    if(r>mid) Modify(rs,l,r,k);
    Pushup(p);
}

int Query(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r) return tr[p].s;
    int mid=tr[p].l+tr[p].r>>1,res=0;
    Pushdown(p);
    if(l<=mid) res+=Query(ls,l,r);
    if(r>mid) res+=Query(rs,l,r);
    return res;
}

void MdyLink(int u,int v,int k){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) std::swap(u,v);
        Modify(1,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) std::swap(u,v);
    Modify(1,id[v],id[u],k);
}

int QryLink(int u,int v){
    int res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) std::swap(u,v);
        res+=Query(1,id[top[u]],id[u]);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) std::swap(u,v);
    res+=Query(1,id[v],id[u]);
    return res;
}

void MdyTree(int u,int k){ Modify(1,id[u],id[u]+siz[u]-1,k); }
int QryTree(int u){ return Query(1,id[u],id[u]+siz[u]-1); }

int main(){
    idx=1; read(n);
    for(int i=2,x;i<=n;i++) read(x),Add(i,x+1),Add(x+1,i);
    Dfs1(1,0), Dfs2(1,1);
    Build(1,1,n);

    char opt[10]; int x;
    read(m);
    while(m--){
        scanf("%s%d",opt,&x); x++;
        if(!strcmp(opt,"install")){
            printf("%d\n",dep[x]-QryLink(1,x));
            MdyLink(1,x,1);
        }else{
            printf("%d\n",QryTree(x));
            MdyTree(x,0);
        }
    }
    return 0;
}

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>

#define rint register int
#define il inline

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

template<class T> inline void read(T &x){
    x=0;char c=getchar();int f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();} x*=f;
}

const int N=100010,M=N<<2;

int n,m,a[N];
int h[N],e[N<<1],ne[N<<1],idx;
int siz[N],id[N],son[N],fa[N],top[N],dep[N],tot;
ll w[N];
struct Sgt{
    int l,r;
    ll s,add;
    void init(int _l,int _r){ l=_l,r=_r,add=0; }
}tr[M];

il void Add(int a,int b){ e[++idx]=b,ne[idx]=h[a],h[a]=idx; }
void Dfs1(int u,int father){
    fa[u]=father;
    siz[u]=1;
    dep[u]=dep[father]+1;
    for(rint i=h[u];i;i=ne[i]){
        int y=e[i];
        if(y==father) continue;
        Dfs1(y,u);
        if(siz[y]>siz[son[u]]) son[u]=y;
        siz[u]+=siz[y];
    }
}
void Dfs2(int u,int f){
    top[u]=f;
    id[u]=++tot;
    w[id[u]]=a[u];
    if(son[u]) Dfs2(son[u],f);
    else return;
    for(rint i=h[u];i;i=ne[i]){
        int y=e[i];
        if(y==fa[u]||y==son[u]) continue;
        Dfs2(y,y); 
    }
}

#define lson p<<1
#define rson p<<1|1
il void Pushup(int p){ tr[p].s=tr[lson].s+tr[rson].s; }
il void Pushdown(int p){
    if(!tr[p].add) return;
    tr[lson].s+=(ll)tr[p].add*(tr[lson].r-tr[lson].l+1);
    tr[rson].s+=(ll)tr[p].add*(tr[rson].r-tr[rson].l+1);
    tr[lson].add+=tr[p].add,tr[rson].add+=tr[p].add;
    tr[p].add=0;
}
void Build(int p,int l,int r){
    tr[p].init(l,r);
    if(l==r){ tr[p].s=w[l]; return; }
    int mid=l+r>>1;
    Build(lson,l,mid); Build(rson,mid+1,r);
    Pushup(p);
}
void Modify(int p,int l,int r,int k){
    if(l<=tr[p].l&&tr[p].r<=r) {
        tr[p].s+=(ll)(tr[p].r-tr[p].l+1)*k;
        tr[p].add+=k;
        return;
    }
    Pushdown(p); int mid=tr[p].l+tr[p].r>>1;
    if(l<=mid) Modify(lson,l,r,k);
    if(r>mid) Modify(rson,l,r,k);
    Pushup(p);
}
ll Query(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r) return tr[p].s;
    Pushdown(p); int mid=tr[p].l+tr[p].r>>1;
    ll sum=0;
    if(l<=mid) sum+=Query(lson,l,r);
    if(r>mid) sum+=Query(rson,l,r);
    return sum;
}
#undef lson
#undef rson

void MdyLink(int u,int v,int k){
    while(top[u]!=top[v])   {
        if(dep[top[u]]<dep[top[v]]) std::swap(u,v);
        Modify(1,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) std::swap(u,v);
    Modify(1,id[v],id[u],k);
}
ll QryLink(int u,int v){
    ll res=0;
    while(top[u]!=top[v])   {
        if(dep[top[u]]<dep[top[v]]) std::swap(u,v);
        res+=Query(1,id[top[u]],id[u]);
        u=fa[top[u]];
    } 
    if(dep[u]<dep[v]) std::swap(u,v);
    res+=Query(1,id[v],id[u]);
    return res;
}
void MdyTree(int u,int k){ Modify(1,id[u],id[u]+siz[u]-1,k); }
ll QryTree(int u){ return Query(1,id[u],id[u]+siz[u]-1); }

int main(){
    read(n); idx=1;
    for(rint i=1;i<=n;i++) read(a[i]);
    for(rint i=0;i<n-1;i++){
        int x,y; read(x),read(y);
        Add(x,y); Add(y,x); 
    }
    Dfs1(1,0); Dfs2(1,1); 
    Build(1,1,n);

    read(m);
    while(m--){
        int opt,u,v,k;
        read(opt);
        switch(opt){
            case 1:
                read(u),read(v),read(k);
                MdyLink(u,v,k);
                break;
            case 2:
                read(u),read(k);
                MdyTree(u,k);
                break;
            case 3:
                read(u),read(v);
                printf("%lld\n",QryLink(u,v));
                break;
            case 4:
                read(u);
                printf("%lld\n",QryTree(u));
                break;
        }
    }   
    return 0;
}

线段树套fhq-treap

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>

#define rint register int
#define il inline 

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

template<class T> inline void read(T &x){
    x=0; char c=getchar(); int f=1;
    while(!isdigit(c)) {if(c=='-') f=-1; c=getchar();}
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}

const int N=50010,M=N<<2;
const int INF=2147483647;

int n,m,tot;
struct Node{
    int s[2],v,key,size;
    void init(int _v){
        v=_v; key=rand();
        size=1;
    }
}fhq[1300010];
struct Sgt{
    int l,r,root;
    void init(int _l,int _r){l=_l;r=_r;}
}tr[M];
int w[N];

il int New(int v){ fhq[++tot].init(v);return tot; }
il void Pushup(int x){ fhq[x].size=fhq[fhq[x].s[0]].size+fhq[fhq[x].s[1]].size+1; }
il void Split(int u,int k,int &x,int &y){
    if(!u){x=y=0; return;}
    if(fhq[u].v<=k) x=u,Split(fhq[u].s[1],k,fhq[u].s[1],y);
    else y=u,Split(fhq[u].s[0],k,x,fhq[u].s[0]);
    Pushup(u);
}
il int Merge(int x,int y){
    if(!x||!y) return x+y;
    if(fhq[x].key>fhq[y].key) {
        fhq[x].s[1]=Merge(fhq[x].s[1],y);
        Pushup(x); return x;
    } else{
        fhq[y].s[0]=Merge(x,fhq[y].s[0]);
        Pushup(y); return y;
    }
}
il void Insert(int p,int v){
    int A,B;
    Split(tr[p].root,v,A,B);
    tr[p].root=Merge(Merge(A,New(v)),B);
}
il void Delete(int p,int v){
    int A,B,C;
    Split(tr[p].root,v,A,C);
    Split(A,v-1,A,B); B=Merge(fhq[B].s[0],fhq[B].s[1]);
    tr[p].root=Merge(Merge(A,B),C);
}

#define ls (p<<1)
#define rs (p<<1|1)
il void Build(int p,int l,int r){
    tr[p].init(l,r);
    Insert(p,-INF); Insert(p,INF);
    for(rint i=l;i<=r;i++) Insert(p,w[i]);
    if(l==r) return;
    int mid=l+r>>1;
    Build(ls,l,mid),Build(rs,mid+1,r);
}

il void Modify(int p,int pos,int v){
    Delete(p,w[pos]);
    Insert(p,v);
    if(tr[p].l==tr[p].r&&tr[p].l==pos){ w[pos]=v; return; }
    int mid=tr[p].l+tr[p].r>>1;
    if(pos<=mid) Modify(ls,pos,v);
    else Modify(rs,pos,v);
}

il int Getrk(int p,int l,int r,int v){
    if(l<=tr[p].l&&tr[p].r<=r) {
        int A,B;
        Split(tr[p].root,v,A,B);
        int ret=fhq[A].size-1;
        tr[p].root=Merge(A,B);
        return ret;
    }   
    int mid=tr[p].l+tr[p].r>>1,sum=0;
    if(l<=mid) sum+=Getrk(ls,l,r,v);
    if(r>mid) sum+=Getrk(rs,l,r,v);
    return sum;
}

il int Getpre(int p,int l,int r,int x){
    if(l<=tr[p].l&&tr[p].r<=r){
        int A,B;
        Split(tr[p].root,x-1,A,B);
        int u=A; while(fhq[u].s[1]) u=fhq[u].s[1];
        tr[p].root=Merge(A,B);
        return fhq[u].v;
    } 
    int mid=tr[p].l+tr[p].r>>1,ret=-INF;
    if(l<=mid) ret=std::max(ret,Getpre(ls,l,r,x));
    if(r>mid) ret=std::max(ret,Getpre(rs,l,r,x));
    return ret;
}

il int Getnxt(int p,int l,int r,int x){
    if(l<=tr[p].l&&tr[p].r<=r){
        int A,B;
        Split(tr[p].root,x,A,B);
        int u=B; while(fhq[u].s[0]) u=fhq[u].s[0];
        tr[p].root=Merge(A,B);
        return fhq[u].v;
    }
    int mid=tr[p].l+tr[p].r>>1,ret=INF;
    if(l<=mid) ret=std::min(ret,Getnxt(ls,l,r,x));
    if(r>mid) ret=std::min(ret,Getnxt(rs,l,r,x));
    return ret;
}
#undef ls
#undef rs

int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++) read(w[i]);
    Build(1,1,n);

    while(m--){
        int opt; read(opt);
        if(opt==1) {
            int l,r,x; read(l),read(r),read(x);
            printf("%d\n",Getrk(1,l,r,x-1)+1);
        } if(opt==2){
            int l,r,k; read(l),read(r),read(k);
            int L=0,R=1e8;
            while(L<R){
                int mid=L+R+1>>1;
                if(Getrk(1,l,r,mid-1)+1<=k) L=mid;
                else R=mid-1; 
            } printf("%d\n",L);
        } if(opt==3){
            int pos,x; read(pos),read(x);
            Modify(1,pos,x);
        } if(opt==4){
            int l,r,x; read(l),read(r),read(x);
            printf("%d\n",Getpre(1,l,r,x));
        } if(opt==5){
            int l,r,x; read(l),read(r),read(x);
            printf("%d\n",Getnxt(1,l,r,x));
        }
    }
    return 0;
}

#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<set>

#define rint register int

using std::multiset;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

template<class T> inline void read(T &x){
    x=0;char c=getchar();int f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();} x*=f;
}

const int N=200010;
const int INF=0x3f3f3f3f;

int n,m;
int a[N];
struct Sgt{
    int l,r;
    multiset<int> s;
}tr[N];

void Build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    tr[p].s.insert(INF); tr[p].s.insert(-INF);
    for(rint i=l;i<=r;i++) tr[p].s.insert(a[i]);
    if(l==r) return;
    int mid=l+r>>1;
    Build(p<<1,l,mid);
    Build(p<<1|1,mid+1,r);
}

void Modify(int p,int pos,int x,int c){
    tr[p].s.erase(tr[p].s.find(x));
    tr[p].s.insert(c);
    if(tr[p].l==tr[p].r&&tr[p].l==pos) return;
    int mid=tr[p].l+tr[p].r>>1;
    if(pos<=mid) Modify(p<<1,pos,x,c);
    else Modify(p<<1|1,pos,x,c);
}

int pre(int p,int l,int r,int x){
    if(l<=tr[p].l&&tr[p].r<=r) 
        return *(--tr[p].s.lower_bound(x));
    int mid=tr[p].l+tr[p].r>>1,res=-INF;
    if(l<=mid) res=std::max(pre(p<<1,l,r,x),res);
    if(r>mid) res=std::max(pre(p<<1|1,l,r,x),res);
    return res;
}

int main(){
    read(n);read(m);
    for(rint i=1;i<=n;i++) read(a[i]);
    Build(1,1,n);   

    int opt,x,y,z;
    while(m--){
        read(opt);
        if(opt==1){
            read(x);read(y);
            Modify(1,x,a[x],y);
            a[x]=y;
        }   else{
            read(x);read(y);read(z);
            printf("%d\n",pre(1,x,y,z));
        }
    }
    return 0;
}

#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>

#define rint register int

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

template<class T> inline void read(T &x){
    x=0;char c=getchar();int f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();} x*=f;
}

const int N=500010;
const int INF=0x3f3f3f3f;

int n,m;
int w[N],nodes[N],tt;
struct Node{
    int s[2],p;
    int v,same,rev;
    int size,sum,ms,ls,rs;
    void init(int _v,int _p){
        v=_v; p=_p;
        same=rev=s[0]=s[1]=0;
        size=1; sum=ms=_v; ms=rs=std::max(0,_v);
    }
}tr[N];
int root;

inline void Pushup(int x){
    Node &u=tr[x],&l=tr[u.s[0]],&r=tr[u.s[1]];
    u.size=l.size+r.size+1;
    u.sum=l.sum+r.sum+u.v;
    u.ls=std::max(l.ls,l.sum+u.v+r.ls);
    u.rs=std::max(r.rs,r.sum+u.v+l.rs);
    u.ms=std::max(std::max(l.ms,r.ms),l.rs+u.v+r.ls);
}

inline void Pushdown(int x){
    Node &u=tr[x],&l=tr[u.s[0]],&r=tr[u.s[1]];
    if(u.same){
        u.same=u.rev=0;
        if(u.s[0]) l.same=1,l.v=u.v,l.sum=l.size*l.v;
        if(u.s[1]) r.same=1,r.v=u.v,r.sum=r.size*r.v;
        if(u.v>0){
            if(u.s[0]) l.ms=l.ls=l.rs=l.sum;
            if(u.s[1]) r.ms=r.ls=r.rs=r.sum;
        }
        else{
            if(u.s[0]) l.ms=l.v,l.ls=l.rs=0;
            if(u.s[1]) r.ms=r.v,r.ls=r.rs=0;
        }
    }
    else if(u.rev){
        u.rev=0; l.rev^=1; r.rev^=1;
        std::swap(l.ls,l.rs); std::swap(r.ls,r.rs);
        std::swap(l.s[0],l.s[1]),std::swap(r.s[0],r.s[1]);
    }
}

inline void Rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    Pushup(y); Pushup(x);
}

inline void Splay(int x,int k){
    while(tr[x].p!=k){
        int y=tr[x].p,z=tr[y].p;
        if(z!=k){
            if((tr[z].s[1]==y)^(tr[y].s[1]==x)) Rotate(x);
            else Rotate(y);
        }
        Rotate(x);
    }
    if(!k) root=x;
}

inline int get_k(int k){
    int u=root;
    while(u){
        Pushdown(u);
        int y=tr[u].s[0];
        if(k<=tr[y].size) u=y;
        else if(k==tr[y].size+1) return u;
        else k-=tr[y].size+1,u=tr[u].s[1];
    }
}

inline int Build(int l,int r,int p){
    int mid=l+r>>1;
    int u=nodes[tt--];
    tr[u].init(w[mid],p);
    if(l<mid) tr[u].s[0]=Build(l,mid-1,u);
    if(mid<r) tr[u].s[1]=Build(mid+1,r,u);
    Pushup(u);
    return u;
}

void Dfs(int u){
    if(tr[u].s[0]) Dfs(tr[u].s[0]);
    if(tr[u].s[1]) Dfs(tr[u].s[1]);
    nodes[++tt]=u;
}

int main(){
    for(rint i=1;i<N;i++) nodes[++tt]=i;
    read(n);read(m);
    tr[0].ms=w[0]=w[n+1]=-INF;
    for(rint i=1;i<=n;i++) read(w[i]);
    root=Build(0,n+1,0);

    char s[20];
    int tot,posi,c; 
    while(m--){
        scanf("%s",s);
        if(!strcmp(s,"INSERT")){
            read(posi);read(tot);
            for(rint i=1;i<=tot;i++) read(w[i]);
            int l=get_k(posi+1),r=get_k(posi+2);
            Splay(l,0); Splay(r,l);
            int u=Build(1,tot,r);
            tr[r].s[0]=u;
            Pushup(r); Pushup(l);
        }
        else if(!strcmp(s,"DELETE")){
            read(posi);read(tot);
            int l=get_k(posi),r=get_k(posi+tot+1);
            Splay(l,0); Splay(r,l);
            Dfs(tr[r].s[0]);
            tr[r].s[0]=0;
            Pushup(r); Pushup(l);
        }
        else if(!strcmp(s,"MAKE-SAME")){
            read(posi); read(tot);read(c);
            int l=get_k(posi),r=get_k(posi+tot+1);
            Splay(l,0); Splay(r,l);
            Node &u=tr[tr[r].s[0]];
            u.v=c,u.same=1,u.sum=c*u.size;
            if(c>0) u.ms=u.ls=u.rs=u.sum;
            else u.ms=u.v,u.ls=u.rs=0;
            Pushup(r); Pushup(l);
        }
        else if(!strcmp(s,"REVERSE")){
            read(posi); read(tot);
            int l=get_k(posi),r=get_k(posi+tot+1);
            Splay(l,0); Splay(r,l);
            Node &u=tr[tr[r].s[0]];
            u.rev^=1; 
            std::swap(u.s[0],u.s[1]);
            std::swap(u.ls,u.rs);
            Pushup(r);Pushup(l);
        }
        else if(!strcmp(s,"GET-SUM")){
            read(posi);read(tot);
            int l=get_k(posi),r=get_k(posi+tot+1);
            Splay(l,0); Splay(r,l);
            printf("%d\n",tr[tr[r].s[0]].sum);
        }
        else printf("%d\n",tr[root].ms);
    }
    return 0;
}

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>

#define rint register int
#define il inline 

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

template<class T> inline void read(T &x){
    x=0; char c=getchar(); int f=1;
    while(!isdigit(c)) {if(c=='-') f=-1; c=getchar();}
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}

const int N=100010,M=1700000;
const int INF=0x3f3f3f3f;

int n,m,q;
int root[N],tot;
struct node{
    int s[2],p;
    int v,id,size;
    void init(int _p,int _v,int _id){
        p=_p;v=_v;id=_id;size=1;
    }
}tr[M];
int fa[N],sz[N];

int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}

il void Pushup(int x){
    tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
}

il void Rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    Pushup(y);Pushup(x);
}

il void Splay(int tree,int x,int k){
    while(tr[x].p!=k){
        int y=tr[x].p,z=tr[y].p;
        if(z!=k){
            if((tr[z].s[1]==y)^(tr[y].s[1]==x)) Rotate(x);
            else Rotate(y);
        }
        Rotate(x);
    }
    if(!k) root[tree]=x;
}

il void Insert(int tree,int v,int id){
    int u=root[tree],p=0;
    while(u) p=u,u=tr[u].s[v>tr[u].v];
    u=++tot;
    if(p) tr[p].s[v>tr[p].v]=u;
    tr[u].init(p,v,id);
    Splay(tree,u,0);  
}

void Dfs(int u,int b){
    if(tr[u].s[0]) Dfs(tr[u].s[0],b);
    Insert(b,tr[u].v,tr[u].id);
    if(tr[u].s[1]) Dfs(tr[u].s[1],b);
}

void Merge(int a,int b){
    a=get(a); b=get(b);
    if(a==b) return;
    if(sz[a]>sz[b]) std::swap(a,b);
    Dfs(root[a],b);
    fa[a]=b,sz[b]+=sz[a];
}

il int K_th(int tree,int x){
    int u=root[tree];
    if(x>tr[u].size) return -1;
    while(1){
        int y=tr[u].s[0];
        if(x<=tr[y].size) u=y;
        else if(x<=tr[y].size+1) {
            Splay(tree,u,0);
            return tr[root[tree]].id;
        }
        else{
            x-=tr[y].size+1;
            u=tr[u].s[1];
        }
    }
}

int main(){
    read(n);read(m);
    for(rint i=1,x;i<=n;i++){
        read(x);
        Insert(i,x,i);
        fa[i]=i; sz[i]=1;
    }
    for(rint i=1,x,y;i<=m;i++){
        read(x);read(y);
        Merge(x,y);
    }
    read(q);
    while(q--){
        char opt[3]; int x,y;
        scanf("%s",opt); read(x);read(y);
        if(*opt=='B') Merge(x,y);
        else printf("%d\n",K_th(get(x),y));
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod=1e9+7;
const int N=50010,M=210;

int T,n,A,B;
int C[M][M],s[N][M];

void init(){
  C[0][0]=1;
  for(int i=1;i<M;i++){
    for(int j=0;j<=i;j++){
      if(!j) C[i][j]=1;
      else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
  }
  s[0][0]=1;
  for(int i=1;i<N;i++)
    for(int j=1;j<=min(M-1,i);j++)
      s[i][j]=((ll)(i-1)*s[i-1][j]+s[i-1][j-1])%mod;
}

int main(){
  init();
  scanf("%d",&T);
  while(T--){
    scanf("%d%d%d",&n,&A,&B);
    printf("%d\n",(ll)C[A+B-2][A-1]*s[n-1][A+B-2]%mod);
  }
  return 0;
}