跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2250. Sereja and Intervals

  • ID: 2256
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 组合数学
  • 动态规划
  • 数学
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Sereja and Intervals

题目描述

E. Sereja and Intervals
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 [l1,r1] belongs to interval [l2,r2] if the following condition is met: l2≤l1≤r1≤r2.

Sereja wants to write out a sequence of n intervals [l1,r1], [l2,r2], ..., [ln,rn] 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 li=x. Sereja wonders, how many distinct ways to write such intervals are there?

Help Sereja and find the required number of ways modulo 1000000007 (109+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 (109+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]}.


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 1858 题。保留原作者与原赛事署名。