【题目描述】

定义一个长度为n的正整数序列A是“好”的序列，当且仅当其满足如下条件：

1.序列中每个数均满足 1≤A[i]≤n

2.i≠j⇔A[i]≠A[j]

3.最长下降子序列长度不超过2

现在有T组询问，每组询问的形式是：有多少个长度为n的“好”的序列，满足A[x]=y。这个答案可能很大，请你求出对10^9+7取模的结果。

【输入数据】

第一行一个非负整数T表示询问组数。

接下来T行，每行三个正整数n、x和y表示询问。

【输出数据】

输出T行，每一行输出询问对应的答案对10^9+7取模的结果。

【数据范围】

Subtask 1 (3pts)：T=0。

Subtask 2 (7pts)：T≤10 n≤8。

Subtask 3 (10pts)：T≤10 n≤15。

Subtask 4 (10pts)：T≤10 n≤200。

Subtask 5 (20pts)：T≤10 n≤2000。

Subtask 6 (20pts)：T≤10 n≤100000。

Subtask 7 (30pts)：无特殊限制。

对于全部数据，有0≤T≤1000000 1≤n≤10000000。

【分析】

1.(3pts)随便读入输出

2.(10pts)暴力枚举每种排列进行判断，单次询问复杂度:O(n!)

3.(20pts)可以推到以下一个重要结论对正解十分重要

结论：对于任意一个数很容易证明要么所有比它小的数都在它前面，要么满足前面所有的数都比它小

然后状压DP，定义dp[i][2^n]表示当前第i位，用了集合S中的数，转移直接枚举当前这一位填谁，单次询问复杂度O(2^n*n)

4.(50pts)观察题意，前面对限制3的应用还不够充分，仔细思考不难发现一种DP，从大到小依次模拟向一个队列中添加数，那么就会有一种极其有趣的情况，如果当前正在考虑的数没有被插到队列的最前面，那么它前面必然有几个数比它大，于是定义dp[i][j]表示当前填到了i，当前的数要填在第j位之前的方按数。那么就有两种转移dp[i][j]->dp[i-1][j+1]即放在队首，另一种dp[i][j]->dp[i-1][k](1<=k<=j)即放在某一个数后面。

此时发现我们并没有考虑T个询问中对x位的要求，由于前面几种做法并不是很难处理而这里需要进行特殊的分类讨论。观察发现，不难得出结论：要么当前位置去掉后现队列依然成立要么就是加上这一位后不存在这两种情况:x之前有大于y的(因为x前如果有那么就会有一个小于y的在它后面于是那个大于的与这一个和后面那个小于的就形成了一个长度为3的下降子序列)或者x之后有小于y的(证明与第一种情况类似)。所以按照x与y的大小关系分为三类：(1)当x=y则按照结论，序列以x为断点分为两个子问题，两段分别符合条件即可。(2)当x>y则一定有比y大的数在x之前，那么需要有比y小的数都在x前，后面一定都是比y大的数所以dp在插入y之前是有一定限制的固定转移。按此策略递推即可。(3)当x<y与上一情况类似，在此不做赘述。单次询问复杂度O(n^2)

这个dp十分细节，还是有几分写的必要(因为正解推公式代码没有任何细节)，这里留个?，以后来填。(懒？)

5.(70pts)

6.(100pts)

#include
    
     #define int long longusing namespace std;const int N=20000005,mod=1e9+7;int x,y,n,t,fac[N],inv[N];inline int C(int u,int v){return (u
     
      <0)?0:fac[u]*inv[v]%mod*inv[u-v]%mod;}signed main(signed argc, char const *argv[]){    // freopen("tg.in","r",stdin);freopen("tg.out","w",stdout);    ios::sync_with_stdio(false);    cin>>t;    fac[1]=fac[0]=inv[0]=inv[1]=1;    for(int i=2;i<=20000000;i++)fac[i]=fac[i-1]*i%mod;    for(int i=2;i<=20000000;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;    for(int i=2;i<=20000000;i++)(inv[i]*=inv[i-1])%=mod;    while(t--)    {        cin>>n>>x>>y;        if(x>y)swap(x,y);        int ansxy=(C(x+y-2,x-1)-C(x+y-2,x-2)+mod)%mod;        int ansyx=(C(2*n-x-y,n-y)-C(2*n-x-y,n-y-1)+mod)%mod;        cout<
      
       <