#include <bits/stdc++.h>
#pragma GCC optimize("O3")
const double pi = std::acos(-1);
using namespace std;
const long long int mod = 1000000000 + 7;
long long int power(long long int x, long long int y, long long int md) {
  long long int res = 1;
  x = x % md;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % md;
    y = y >> 1;
    x = (x * x) % md;
  }
  return res;
}
long long int m_mul(long long int a, long long int b) {
  a = a % mod;
  b = b % mod;
  return (a * b + mod) % mod;
}
long long int m_add(long long int a, long long int b) {
  a = a % mod;
  b = b % mod;
  return (a + b + mod) % mod;
}
long long int spf[(long long int)1e7 + 2] = {0};
struct dsu {
  vector<long long int> parent, rank;
  dsu(long long int n) {
    parent.resize(n + 2);
    rank.resize(n + 2);
  }
  long long int fnd(long long int i) {
    if (parent[i] == i)
      return i;
    else
      return fnd(parent[i]);
  }
  void unite(long long int a, long long int b) {
    if (rank[a] > rank[b])
      parent[b] = a;
    else if (rank[b] > rank[a])
      parent[a] = b;
    else {
      parent[a] = b;
      rank[b]++;
    }
  }
  bool same(long long int a, long long int b) { return fnd(a) == fnd(b); }
};
struct sgtree {
  vector<long long int> arr;
  vector<long long int> tree, lazy;
  sgtree(long long int n, long long int brr[]) {
    arr.resize(n);
    long long int k = 2 * (long long int)powl(2, log2l(n) + 1);
    tree.resize(k);
    lazy.resize(k);
    for (long long int i = 0; i < k; i++) lazy[i] = -1;
    for (long long int i = 0; i < n; i++) arr[i] = brr[i];
  }
  void build(long long int ind, long long int left, long long int right) {
    if (left == right) {
      tree[ind] = arr[left];
      return;
    }
    long long int mid = left + (right - left) / 2;
    build(2 * ind + 1, left, mid);
    build(2 * ind + 2, mid + 1, right);
    tree[ind] = tree[2 * ind + 1] + tree[2 * ind + 2];
  }
  void updateSingle(long long int ind, long long int index, long long int val,
                    long long int left, long long int right) {
    if (left == right && left == index) {
      tree[ind] = val;
      return;
    }
    if (index > right || index < left) return;
    long long int mid = left + (right - left) / 2;
    updateSingle(2 * ind + 1, index, val, left, mid);
    updateSingle(2 * ind + 2, index, val, mid + 1, right);
    tree[ind] = tree[2 * ind + 1] + tree[2 * ind + 2];
  }
  void updateLazy(long long int ind, long long int indexleft,
                  long long int indexright, long long int val,
                  long long int left, long long int right) {
    if (lazy[ind] != -1) {
      tree[ind] = (right - left + 1) * lazy[ind];
      if (left != right) {
        lazy[2 * ind + 1] = lazy[ind];
        lazy[2 * ind + 2] = lazy[ind];
      }
      lazy[ind] = -1;
    }
    if (indexleft > right || indexright < left) return;
    if (indexleft <= left && right <= indexright) {
      tree[ind] = (right - left + 1) * val;
      if (left != right) {
        lazy[2 * ind + 1] = val;
        lazy[2 * ind + 2] = val;
      }
      return;
    }
    long long int mid = left + (right - left) / 2;
    updateLazy(2 * ind + 1, indexleft, indexright, val, left, mid);
    updateLazy(2 * ind + 2, indexleft, indexright, val, mid + 1, right);
    tree[ind] = tree[2 * ind + 1] + tree[2 * ind + 2];
  }
  long long int ans(long long int ind, long long int start, long long int end,
                    long long int left, long long int right) {
    if (lazy[ind] != -1) {
      tree[ind] = (right - left + 1) * lazy[ind];
      if (left != right) {
        lazy[2 * ind + 1] = lazy[ind];
        lazy[2 * ind + 2] = lazy[ind];
      }
      lazy[ind] = -1;
    }
    if (left > end || start > right) return 0;
    if (start <= left && right <= end) return tree[ind];
    long long int mid = left + (right - left) / 2;
    return ans(2 * ind + 1, start, end, left, mid) +
           ans(2 * ind + 2, start, end, mid + 1, right);
  }
};
void siv() {
  spf[1] = 1;
  for (long long int i = 1; i < 1e7 + 2; i++) spf[i] = i;
  for (long long int i = 2; i < 1e7 + 2; i++) spf[i] = 2, i++;
  for (long long int i = 3; i * i < (long long int)1e7 + 2; i++) {
    if (spf[i] == i)
      for (long long int j = i * i; j < (long long int)1e7 + 2; j = j + i)
        if (spf[j] == j) spf[j] = i;
  }
}
void fn(long long int n, long long int x, long long int pos, long long int &k1,
        long long int &k2) {
  long long int l = 0, r = n;
  long long int fl = 0;
  while (l < r) {
    long long int mid = (l + r) / 2;
    if (mid < pos && fl == 0) {
      l = mid + 1;
      k1++;
    } else if (mid == pos) {
      l = mid + 1;
      fl = 1;
    } else {
      r = mid;
      k2++;
    }
  }
}
const int N = 1000001;
long long int factorialNumInverse[N + 1];
long long int naturalNumInverse[N + 1];
long long int fact[N + 1];
void InverseofNumber(long long int p) {
  naturalNumInverse[0] = naturalNumInverse[1] = 1;
  for (int i = 2; i <= N; i++)
    naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
void InverseofFactorial(long long int p) {
  factorialNumInverse[0] = factorialNumInverse[1] = 1;
  for (int i = 2; i <= N; i++)
    factorialNumInverse[i] =
        (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}
void factorial(long long int p) {
  fact[0] = 1;
  for (int i = 1; i <= N; i++) {
    fact[i] = (fact[i - 1] * i) % p;
  }
}
long long int ncr(long long int N, long long int R, long long int p) {
  if (N - R < 0) return 0;
  long long int ans =
      ((fact[N] * factorialNumInverse[R]) % p * factorialNumInverse[N - R]) % p;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  long long int tc = 1;
  long long int p = 1000000007;
  InverseofNumber(p);
  InverseofFactorial(p);
  factorial(p);
  while (tc--) {
    long long int n, x, pos;
    cin >> n >> x >> pos;
    long long int k1 = 0, k2 = 0;
    fn(n, x, pos, k1, k2);
    long long int a1 = (ncr(x - 1, k1, p) % mod * fact[k1] % mod) % mod;
    long long int a2 = (ncr(n - (x), k2, p) % mod * fact[k2] % mod) % mod;
    a1 = (a1 % mod * a2 % mod) % mod;
    a1 = (a1 % mod * fact[n - (k1 + k2 + 1)] % mod) % mod;
    cout << a1 << '\n';
  }
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

Andrey thinks he is truly a successful developer, but in reality he didn't know about the binary search algorithm until recently. After reading some literature Andrey understood that this algorithm allows to quickly find a certain number x in an array. For an array a indexed from zero, and an integer x the pseudocode of the algorithm is as follows:

<image>

Note that the elements of the array are indexed from zero, and the division is done in integers (rounding down).

Andrey read that the algorithm only works if the array is sorted. However, he found this statement untrue, because there certainly exist unsorted arrays for which the algorithm find x!

Andrey wants to write a letter to the book authors, but before doing that he must consider the permutations of size n such that the algorithm finds x in them. A permutation of size n is an array consisting of n distinct integers between 1 and n in arbitrary order.

Help Andrey and find the number of permutations of size n which contain x at position pos and for which the given implementation of the binary search algorithm finds x (returns true). As the result may be extremely large, print the remainder of its division by 10^9+7.

Input

The only line of input contains integers n, x and pos (1 ≤ x ≤ n ≤ 1000, 0 ≤ pos ≤ n - 1) — the required length of the permutation, the number to search, and the required position of that number, respectively.

Output

Print a single number — the remainder of the division of the number of valid permutations by 10^9+7.

Examples

Input


4 1 2


Output


6


Input


123 42 24


Output


824071958

Note

All possible permutations in the first test case: (2, 3, 1, 4), (2, 4, 1, 3), (3, 2, 1, 4), (3, 4, 1, 2), (4, 2, 1, 3), (4, 3, 1, 2).

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
const double pi = std::acos(-1);
using namespace std;
const long long int mod = 1000000000 + 7;
long long int power(long long int x, long long int y, long long int md) {
  long long int res = 1;
  x = x % md;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % md;
    y = y >> 1;
    x = (x * x) % md;
  }
  return res;
}
long long int m_mul(long long int a, long long int b) {
  a = a % mod;
  b = b % mod;
  return (a * b + mod) % mod;
}
long long int m_add(long long int a, long long int b) {
  a = a % mod;
  b = b % mod;
  return (a + b + mod) % mod;
}
long long int spf[(long long int)1e7 + 2] = {0};
struct dsu {
  vector<long long int> parent, rank;
  dsu(long long int n) {
    parent.resize(n + 2);
    rank.resize(n + 2);
  }
  long long int fnd(long long int i) {
    if (parent[i] == i)
      return i;
    else
      return fnd(parent[i]);
  }
  void unite(long long int a, long long int b) {
    if (rank[a] > rank[b])
      parent[b] = a;
    else if (rank[b] > rank[a])
      parent[a] = b;
    else {
      parent[a] = b;
      rank[b]++;
    }
  }
  bool same(long long int a, long long int b) { return fnd(a) == fnd(b); }
};
struct sgtree {
  vector<long long int> arr;
  vector<long long int> tree, lazy;
  sgtree(long long int n, long long int brr[]) {
    arr.resize(n);
    long long int k = 2 * (long long int)powl(2, log2l(n) + 1);
    tree.resize(k);
    lazy.resize(k);
    for (long long int i = 0; i < k; i++) lazy[i] = -1;
    for (long long int i = 0; i < n; i++) arr[i] = brr[i];
  }
  void build(long long int ind, long long int left, long long int right) {
    if (left == right) {
      tree[ind] = arr[left];
      return;
    }
    long long int mid = left + (right - left) / 2;
    build(2 * ind + 1, left, mid);
    build(2 * ind + 2, mid + 1, right);
    tree[ind] = tree[2 * ind + 1] + tree[2 * ind + 2];
  }
  void updateSingle(long long int ind, long long int index, long long int val,
                    long long int left, long long int right) {
    if (left == right && left == index) {
      tree[ind] = val;
      return;
    }
    if (index > right || index < left) return;
    long long int mid = left + (right - left) / 2;
    updateSingle(2 * ind + 1, index, val, left, mid);
    updateSingle(2 * ind + 2, index, val, mid + 1, right);
    tree[ind] = tree[2 * ind + 1] + tree[2 * ind + 2];
  }
  void updateLazy(long long int ind, long long int indexleft,
                  long long int indexright, long long int val,
                  long long int left, long long int right) {
    if (lazy[ind] != -1) {
      tree[ind] = (right - left + 1) * lazy[ind];
      if (left != right) {
        lazy[2 * ind + 1] = lazy[ind];
        lazy[2 * ind + 2] = lazy[ind];
      }
      lazy[ind] = -1;
    }
    if (indexleft > right || indexright < left) return;
    if (indexleft <= left && right <= indexright) {
      tree[ind] = (right - left + 1) * val;
      if (left != right) {
        lazy[2 * ind + 1] = val;
        lazy[2 * ind + 2] = val;
      }
      return;
    }
    long long int mid = left + (right - left) / 2;
    updateLazy(2 * ind + 1, indexleft, indexright, val, left, mid);
    updateLazy(2 * ind + 2, indexleft, indexright, val, mid + 1, right);
    tree[ind] = tree[2 * ind + 1] + tree[2 * ind + 2];
  }
  long long int ans(long long int ind, long long int start, long long int end,
                    long long int left, long long int right) {
    if (lazy[ind] != -1) {
      tree[ind] = (right - left + 1) * lazy[ind];
      if (left != right) {
        lazy[2 * ind + 1] = lazy[ind];
        lazy[2 * ind + 2] = lazy[ind];
      }
      lazy[ind] = -1;
    }
    if (left > end || start > right) return 0;
    if (start <= left && right <= end) return tree[ind];
    long long int mid = left + (right - left) / 2;
    return ans(2 * ind + 1, start, end, left, mid) +
           ans(2 * ind + 2, start, end, mid + 1, right);
  }
};
void siv() {
  spf[1] = 1;
  for (long long int i = 1; i < 1e7 + 2; i++) spf[i] = i;
  for (long long int i = 2; i < 1e7 + 2; i++) spf[i] = 2, i++;
  for (long long int i = 3; i * i < (long long int)1e7 + 2; i++) {
    if (spf[i] == i)
      for (long long int j = i * i; j < (long long int)1e7 + 2; j = j + i)
        if (spf[j] == j) spf[j] = i;
  }
}
void fn(long long int n, long long int x, long long int pos, long long int &k1,
        long long int &k2) {
  long long int l = 0, r = n;
  long long int fl = 0;
  while (l < r) {
    long long int mid = (l + r) / 2;
    if (mid < pos && fl == 0) {
      l = mid + 1;
      k1++;
    } else if (mid == pos) {
      l = mid + 1;
      fl = 1;
    } else {
      r = mid;
      k2++;
    }
  }
}
const int N = 1000001;
long long int factorialNumInverse[N + 1];
long long int naturalNumInverse[N + 1];
long long int fact[N + 1];
void InverseofNumber(long long int p) {
  naturalNumInverse[0] = naturalNumInverse[1] = 1;
  for (int i = 2; i <= N; i++)
    naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
void InverseofFactorial(long long int p) {
  factorialNumInverse[0] = factorialNumInverse[1] = 1;
  for (int i = 2; i <= N; i++)
    factorialNumInverse[i] =
        (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}
void factorial(long long int p) {
  fact[0] = 1;
  for (int i = 1; i <= N; i++) {
    fact[i] = (fact[i - 1] * i) % p;
  }
}
long long int ncr(long long int N, long long int R, long long int p) {
  if (N - R < 0) return 0;
  long long int ans =
      ((fact[N] * factorialNumInverse[R]) % p * factorialNumInverse[N - R]) % p;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  long long int tc = 1;
  long long int p = 1000000007;
  InverseofNumber(p);
  InverseofFactorial(p);
  factorial(p);
  while (tc--) {
    long long int n, x, pos;
    cin >> n >> x >> pos;
    long long int k1 = 0, k2 = 0;
    fn(n, x, pos, k1, k2);
    long long int a1 = (ncr(x - 1, k1, p) % mod * fact[k1] % mod) % mod;
    long long int a2 = (ncr(n - (x), k2, p) % mod * fact[k2] % mod) % mod;
    a1 = (a1 % mod * a2 % mod) % mod;
    a1 = (a1 % mod * fact[n - (k1 + k2 + 1)] % mod) % mod;
    cout << a1 << '\n';
  }
  return 0;
}

```