[USACO21DEC] HILO P
题目描述
Bessie 有一个数 $x+0.5$,其中 $x$ 是某个 $0$ 到 $N$ 之间的整数($1\le N\le 5000$)。
Elsie 正试着猜这个数。她可以以如下形式对于某个 $1$ 到 $N$ 之间的整数提问:「$i$ 是大了还是小了?」如果 $i$ 大于 $x+0.5$,Bessie 会回答 "HI!",如果 $i$ 小于 $x+0.5$ 则回答 "LO!"。
Elsie 想到了以下猜测 Bessie 的数的策略。在进行任何猜测之前,她创建了一个包含 $N$ 个整数的序列,其中从 $1$ 到 $N$ 的每个数均恰好出现一次(换句话说,这个序列是长为 $N$ 的一个排列)。然后她遍历这一列表,按列表中的数的顺序依次猜数。然而,Elsie 会跳过所有不必要的猜测。也就是说,如果 Elsie 将要猜某个数 $i$,而 Elsie 之前已经猜过了某个 $j < i$ 并且 Bessie 回答 "HI!",Elsie 不会再猜 $i$,而是继续猜序列中的下一个数。类似地,如果她将要猜某个数 $i$,而她之前已经猜过了某个 $j > i$ 并且 Bessie 回答 "LO!",Elsie 不会再猜 $i$,而是继续猜序列中的下一个数。可以证明,使用这一策略,对于 Elsie 创建的任意序列,她都可以唯一确定 $x$。
如果我们将所有 Bessie 回答的 "HI" 或 "LO" 拼接成一个字符串 $S$,那么 Bessie 说 "HILO" 的次数为 $S$ 等于 "HILO" 的长为 $4$ 的子串数量。
Bessie 知道 Elsie 将要使用这一策略,并且已经选定了值 $x$,但她不知道 Elsie 会使用什么排列。你的目标是对于所有 Elsie 可能选用的排列,计算 Bessie 说 "HILO" 的次数之和,对 $10^9+7$ 取模。
输入输出格式
输入格式
输入一行,包含 $N$ 和 $x$。
输出格式
输出 HILO 的总数,对 $10^9+7$ 取模。
输入输出样例
输入样例 #1
4 2
输出样例 #1
17
输入样例 #2
60 10
输出样例 #2
508859913
说明
【样例解释1】
在这个测试用例中,Bessie 的数是 $2.5$。
例如,如果 Elsie 的排列是 $(4,1,3,2)$,那么 Bessie 会说 ""HILOHILO",总计两次 "HILO"。又例如,如果 Elsie 的排列是 $(3,1,2,4)$,那么 Bessie 会说 "HILOLO",总计一次 "HILO"。
【样例解释2】
确保输出总和对 $10^9+7$ 取模的结果。
【数据范围】
- 测试点 3-10 满足 $N\le 50$;
- 测试点 11-18 满足 $N\le 500$;
- 测试点 19-26 没有额外限制。