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)
TC发现,在某些情况下,即使序列并不有序,他的二分查找依然能够成功,TC兴奋不已!
现在,给定n,x,请你来帮TC求出魔法序列数。
[hhh,哪有什么魔法序列,当然是用来骗TC的啦~]
Input
两个整数n,x(1<=n,x<=106)
Output
一个整数,表示魔法序列数目(答案很大,对1e9+7取模)
HINT
对于样例n=3,x=1
序列[1,2,3],[1,3,2],[2,1,3],[3,1,2]均可成功查找1,
所以魔法序列数为4。