#P7986. [USACO21DEC] HILO P

[USACO21DEC] HILO P

题目描述

Bessie 有一个数 x+0.5x+0.5,其中 xx 是某个 00NN 之间的整数(1N50001\le N\le 5000)。

Elsie 正试着猜这个数。她可以以如下形式对于某个 11NN 之间的整数提问:「ii 是大了还是小了?」如果 ii 大于 x+0.5x+0.5,Bessie 会回答 "HI!",如果 ii 小于 x+0.5x+0.5 则回答 "LO!"。

Elsie 想到了以下猜测 Bessie 的数的策略。在进行任何猜测之前,她创建了一个包含 NN 个整数的序列,其中从 11NN 的每个数均恰好出现一次(换句话说,这个序列是长为 NN 的一个排列)。然后她遍历这一列表,按列表中的数的顺序依次猜数。然而,Elsie 会跳过所有不必要的猜测。也就是说,如果 Elsie 将要猜某个数 ii,而 Elsie 之前已经猜过了某个 j<ij < i 并且 Bessie 回答 "HI!",Elsie 不会再猜 ii,而是继续猜序列中的下一个数。类似地,如果她将要猜某个数 ii,而她之前已经猜过了某个 j>ij > i 并且 Bessie 回答 "LO!",Elsie 不会再猜 ii,而是继续猜序列中的下一个数。可以证明,使用这一策略,对于 Elsie 创建的任意序列,她都可以唯一确定 xx

如果我们将所有 Bessie 回答的 "HI" 或 "LO" 拼接成一个字符串 SS,那么 Bessie 说 "HILO" 的次数为 SS 等于 "HILO" 的长为 44 的子串数量。

Bessie 知道 Elsie 将要使用这一策略,并且已经选定了值 xx,但她不知道 Elsie 会使用什么排列。你的目标是对于所有 Elsie 可能选用的排列,计算 Bessie 说 "HILO" 的次数之和,对 109+710^9+7 取模。

输入格式

输入一行,包含 NNxx

输出格式

输出 HILO 的总数,对 109+710^9+7 取模。

4 2
17
60 10
508859913

提示

【样例解释1】

在这个测试用例中,Bessie 的数是 2.52.5

例如,如果 Elsie 的排列是 (4,1,3,2)(4,1,3,2),那么 Bessie 会说 ""HILOHILO",总计两次 "HILO"。又例如,如果 Elsie 的排列是 (3,1,2,4)(3,1,2,4),那么 Bessie 会说 "HILOLO",总计一次 "HILO"。

【样例解释2】

确保输出总和对 109+710^9+7 取模的结果。

【数据范围】

  • 测试点 3-10 满足 N50N\le 50
  • 测试点 11-18 满足 N500N\le 500
  • 测试点 19-26 没有额外限制。