HILO

베시는 \(x+0.5\)라는 수를 알고 있다. 여기서 \(x\)는 \(0\) 이상 \(N\) 이하의 어떤 정수이다(\(1\le N\le 5000\)).

엘시는 이 수를 맞히려 하고 있다. 엘시는 \(1\) 이상 \(N\) 이하의 어떤 정수 \(i\)에 대해 "\(i\)는 높은가 낮은가?" 형태의 질문을 할 수 있다. 베시는 \(i\)가 \(x+0.5\)보다 크면 "HI!", \(i\)가 \(x+0.5\)보다 작으면 "LO!"라고 답한다.

엘시는 베시의 수를 맞히기 위해 다음 전략을 세운다. 추측을 시작하기 전에, 엘시는 \(1\)부터 \(N\)까지의 모든 수가 정확히 한 번씩 등장하는 \(N\)개의 수의 목록을 만든다(다시 말해, 이 목록은 크기 \(N\)의 순열이다). 그런 다음 목록을 따라가며 목록에 등장하는 순서대로 수를 추측한다. 다만, 엘시는 불필요한 추측은 건너뛴다. 즉, 엘시가 어떤 수 \(i\)를 추측하려고 할 때 이전에 어떤 \(j < i\)를 추측했고 베시가 "HI!"라고 답했다면, 엘시는 \(i\)를 추측하지 않고 목록의 다음 수로 넘어간다. 마찬가지로, 어떤 수 \(i\)를 추측하려고 할 때 이전에 어떤 \(j > i\)를 추측했고 베시가 "LO!"라고 답했다면, 엘시는 \(i\)를 추측하지 않고 목록의 다음 수로 넘어간다. 이 전략을 사용하면 엘시가 어떤 순열을 만들더라도 항상 \(x\)를 유일하게 결정할 수 있음을 증명할 수 있다.

베시의 "HI" 또는 "LO" 응답을 모두 이어붙여 하나의 문자열 \(S\)를 만들었을 때, 베시가 "HILO"라고 말한 횟수는 \(S\)의 길이 \(4\)인 부분 문자열 중 "HILO"와 같은 것의 개수이다.

베시는 엘시가 이 전략을 사용할 것임을 알고 있고 \(x\) 값을 이미 정했지만, 엘시가 어떤 순열을 사용할지는 모른다. 엘시가 선택할 수 있는 모든 순열에 대해 베시가 "HILO"를 말하는 횟수의 합을 \(10^9+7\)로 나눈 나머지를 구하는 것이 목표이다.

출제자: Richard Qi

배점

• 테스트 케이스 3-10은 \(N\le 50\)을 만족한다.
• 테스트 케이스 11-18은 \(N\le 500\)을 만족한다.
• 테스트 케이스 19-26은 추가 제약이 없다.

출제자: Richard Qi

입력은 한 줄로 이루어지며, \(N\)과 \(x\)가 주어진다.

HILO의 총 횟수를 \(10^9+7\)로 나눈 나머지를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > December > Platinum