CodeForces - 367E：Sereja and Intervals（组合数&&DP）

Sereja is interested in intervals of numbers, so he has prepared a problem about intervals for you. An interval of numbers is a pair of integers [l, r] (1 ≤ l ≤ r ≤ m). Interval [l₁, r₁] belongs to interval [l₂, r₂] if the following condition is met: l₂ ≤ l₁ ≤ r₁ ≤ r₂.

Sereja wants to write out a sequence of n intervals [l₁, r₁], [l₂, r₂], ..., [l_n, r_n] on a piece of paper. At that, no interval in the sequence can belong to some other interval of the sequence. Also, Sereja loves number x very much and he wants some (at least one) interval in the sequence to have l_i = x. Sereja wonders, how many distinct ways to write such intervals are there?

Help Sereja and find the required number of ways modulo 1000000007 (10⁹ + 7).

Two ways are considered distinct if there is such j (1 ≤ j ≤ n), that the j-th intervals in two corresponding sequences are not equal.

Input

The first line contains integers n, m, x (1 ≤ n·m ≤ 100000, 1 ≤ x ≤ m) — the number of segments in the sequence, the constraints on the numbers in segments and Sereja's favourite number.

Output

In a single line print the answer modulo 1000000007 (10⁹ + 7).

Examples

Input

1 1 1

Output

Input

3 5 1

Output

Input

2 3 3

Output

Note

In third example next sequences will be correct: {[1, 1], [3, 3]}, {[1, 2], [3, 3]}, {[2, 2], [3, 3]}, {[3, 3], [1, 1]}, {[3, 3], [2, 2]}, {[3, 3], [1, 2]}.

题意：给定长度为M的数轴，让你选择N个带编号的线段，使得没有线段有包含关系。给定X，让你至少选择了一个左端点为X的线段。

思路：N<=M; 所以N<sqrt(N*M)<=330；没有包含关系，那么线段A的左端点大于B的左端点，那么A的右端点也一定大于B的右端点。所以我们可以自己去匹配。只保存当点左端点和右端点个数即可。

用dp[i][j][x]表示前x个点选择了i个左端点，j个右端点，不难得到方程。由于x可能有点大，我们用滚动数组。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const int Mod=1e9+;

int dp[maxn][maxn][];

int main()

{

    int N,M,X;

    scanf("%d%d%d",&N,&M,&X);

    if(N>M) return puts(""),;

    dp[][][]=;

    rep(k,,M){//位置

      rep(i,,min(N,M)){ //左括号

        rep(j,,i){ //右括号

            int p=k&;

            if(k==X){

                dp[i][j][p]=;

                if(i>j) (dp[i][j][p]+=dp[i-][j][p^])%=Mod; //左

                if(i&&j) (dp[i][j][p]+=dp[i-][j-][p^])%=Mod;//左+右

            }

            else {

                dp[i][j][p]=dp[i][j][p^]; //不放

                if(i>j) (dp[i][j][p]+=dp[i-][j][p^])%=Mod; //左

                if(i&&j) (dp[i][j][p]+=dp[i-][j-][p^])%=Mod;//左+右

                if(j) (dp[i][j][p]+=dp[i][j-][p^])%=Mod;//右

            }

        }

      }

    }

    rep(i,,N) dp[N][N][M&]=1LL*dp[N][N][M&]*i%Mod;

    printf("%d\n",dp[N][N][M&]);

    return ;

}

巴特西

CodeForces - 367E：Sereja and Intervals（组合数&&DP）

最新文章

热门文章