Sereja and Intervals

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

1

input

3 5 1

output

240

input

2 3 3

output

6

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]}.

Solution:

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

const long long md = 1000000007;
const int N = 333;

int f[N][N], nf[N][N];

int main() {
int n, m, x;
scanf("%d %d %d", &n, &m, &x);
if (n > m) {
printf("%d\n", 0);
return 0;
}
for (int i = 0; i <= n; i++)
    for (int j = 0; j <= i; j++) f[i][j] = 0;
  f[0][0] = 1;
  for (int v = 1; v <= m; v++) {
    for (int i = 0; i <= n; i++)
      for (int j = 0; j <= i; j++) nf[i][j] = 0;
    for (int i = 0; i <= n; i++)
      for (int j = 0; j <= i; j++)
        for (int dx = (v == x); dx <= 1 && i + dx <= n; dx++)
          for (int dy = 0; dy <= 1 && j + dy <= i + dx; dy++) {
            nf[i + dx][j + dy] += f[i][j];
            if (nf[i + dx][j + dy] >= md) nf[i + dx][j + dy] -= md;
}
for (int i = 0; i <= n; i++)
      for (int j = 0; j <= i; j++) f[i][j] = nf[i][j];
  }
  int ans = f[n][n];
  for (int i = 1; i <= n; i++) ans = (long long)ans * i % md;
  printf("%d\n", ans);
  return 0;
}