301939: CF367E. Sereja and Intervals
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Sereja and Intervals
题意翻译
有 $n$ 个区间,你需要为每个区间分配左右端点,端点属于 $[1,m]\cap \mathbb{N}$。你需要保证区间两两互不包含且至少存在一个区间的左端点等于 $x$,输出方案数对 $10^9+7$ 取模的结果,区间有标号。$nm\leqslant 10^5$,$1\leqslant x\leqslant m$。题目描述
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_{1},r_{1}] $ belongs to interval $ [l_{2},r_{2}] $ if the following condition is met: $ l_{2}<=l_{1}<=r_{1}<=r_{2} $ . Sereja wants to write out a sequence of $ n $ intervals $ [l_{1},r_{1}] $ , $ [l_{2},r_{2}] $ , $ ... $ , $ [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^{9}+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.输入输出格式
输入格式
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.
输出格式
In a single line print the answer modulo $ 1000000007 $ $ (10^{9}+7) $ .
输入输出样例
输入样例 #1
1 1 1
输出样例 #1
1
输入样例 #2
3 5 1
输出样例 #2
240
输入样例 #3
2 3 3
输出样例 #3
6