Problem1943--TC的魔法序列(上)

1943: TC的魔法序列(上)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

TC最近一直在研究魔法序列,为此已经两天没背英语单词了。
首先,TC的二分伪代码如下:
BinarySearh(a,x,n)
    left=1
    right=n
    while left<=right
        mid=(left+right)/2[注:这里向下取整]
        if x>a[mid] then
            left=mid+1 
        else if x<a[mid] then
            right=mid-1
        else 
           return  true 
    return false 
在序列元素值[1,2...n]范围内,对于给定的查找元素x(1<=x<=n),其在序列中的位置pos(1<=pos<=n),
TC发现,在某些情况下,即使序列并不有序,他的二分查找依然能够成功,TC兴奋不已!
现在,给定n,x,pos,请你来帮TC求出魔法序列数。
[hhh,哪有什么魔法序列,当然是用来骗TC的啦~]

Input

三个整数n,x,pos(1<=n,x,pos<=1000)

Output

一个整数,表示魔法序列数目(答案很大,对1e9+7取模)

Sample Input Copy

4 1 2

Sample Output Copy

6

HINT

对于样例n=4,x=1,pos=2, 
序列[2,1,3,4],[2,1,4,3],[3,1,2,4],[3,1,4,2],[4,1,2,3],[4,1,3,2]均可成功查找1,
所以魔法序列数为6。