<h2>题目描述</h2>

计数。有多少个长度为 $n$ 的排列，使得可以通过栈排好序并且第 $ps$ 个位置是 $x$。
$n \leq 10^6$

<h2>题解</h2>

首先我们考虑反过来：变成问你 $1 \cdots n$ 的排列通过栈可以生成多少在 $ps$ 位置为 $x$ 的序列。
考虑将这个过程抽象成括号序列：长度为 2n 的括号序列，左括号表示入栈，右括号表示出栈。
那么我们实际上是为了计数长度为 $2n$ 的括号序列，满足第 $ps$ 个左括号和第 $x$ 个右括号是配对在一起的。我们可以枚举左括号在哪里，就可以唯一确定右括号在哪里。分成了三个不同的括号序列都用卡特兰数算一算就好了。
大概是长得这样：
.......(.......).......
首先 ( 和 ) 之间的左右括号数一定相等（也就是保证这两个括号匹配上）
我们枚举 ( 的位置是 $l$，可以轻易算出。（可以看代码）

/*
 * Author: RainAir
 * Time: 2019-11-01 21:53:24
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 4e6 + 5;
const int ha = 1e9 + 7;
int fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1llresa%ha;
        a = 1llaa%ha;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;
    FOR(i,1,MAXN-1) fac[i] = 1llfac[i-1]i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1llinv[i+1](i+1)%ha;
}

inline int C(int n,int m){
    if(n < m) return 0;
    return 1llfac[n]inv[m]%ha*inv[n-m]%ha;
}

inline int F(int n,int m){
    if(n < m) return 0;
    if(n < 0 || m < 0) return 0;
    return (C(n+m,n)+ha-C(n+m,n+1))%ha;
}

int ans = 0;
int n,ps,x;

int main(){
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    scanf("%d%d%d",&n,&ps,&x);
    prework();
    FOR(l,1,2*n){
        (ans += 1llF(ps-1,l-ps)F(ps+x-l-1,ps+x-l-1)%haF(n-x,n-2ps-x+l+1)%ha) %= ha;
    }
    printf("%dn",ans);
    return 0;
}