HILO

题目描述

Bessie 知道一个数 $x+0.5$，其中 $x$ 是一个在 $0$ 到 $N$（含端点）之间的整数（$1\le N\le 5000$）。 Elsie 正在尝试猜这个数。她可以提出形如“$i$ 高还是低？”的问题，其中 $i$ 是 $1$ 到 $N$（含端点）之间的某个整数。若 $i$ 大于 $x+0.5$，Bessie 回答“HI!”；若 $i$ 小于 $x+0.5$，Bessie 回答“LO!”。

Elsie 想出了如下策略来猜 Bessie 的数。在进行任何猜测之前，她先创建一个包含 $N$ 个数的列表，其中从 $1$ 到 $N$ 的每个数恰好出现一次（换言之，这个列表是一个长度为 $N$ 的排列）。然后，她按列表顺序依次猜列表中出现的数。不过，Elsie 会跳过任何不必要的猜测。也就是说，如果 Elsie 准备猜某个数 $i$，并且她之前猜过某个 $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$ 取模后的结果。

4 2

17

60 10

508859913

提示

在该测试用例中，Bessie 的数是 $2.5$。 例如，如果 Elsie 的排列是 $(4,1,3,2)$，那么 Bessie 会说 "HILOHILO," 共出现两个 "HILO"。再例如，如果 Elsie 的排列是 $(3,1,2,4)$，那么 Bessie 会说 "HILOLO," 共出现一个 "HILO。" 请确保输出对 $10^9+7$ 取模后的和。 SCORING: 测试点 3-10 满足 $N\le 50$。 测试点 11-18 满足 $N\le 500$。 测试点 19-26 没有额外限制。 题目出题人：Richard Qi

标签: USACO|2021|Platinum

来源

USACO|2021|Platinum