#USACOC2211C. HILO

HILO

Description

Bessie knows a number x+0.5x+0.5 where xx is some integer between 00 to N,N,inclusive.

Elsie is trying to guess this number. She can ask questions of the form "is iihigh or low?" for some integer ii between 11 and N,N, inclusive. Bessieresponds by saying "HI!" if ii is greater than x+0.5x+0.5, or "LO!" if ii is lessthan x+0.5x+0.5.

Elsie comes up with the following strategy for guessing Bessie's number. Beforemaking any guesses, she creates a list of NN numbers, where every number from11 to NN occurs exactly once (in other words, the list is a permutation ofsize NN.) Then, she goes through the list, guessing numbers that appear in thelist in order. However, Elsie skips any unnecessary guesses. That is, if Elsieis about to guess some number ii and Elsie previously guessed some j<ij < i suchthat Bessie responded with "HI!," Elsie will not guess ii and will move on tothe next number in the list. Similarly, if she is about to guess some number iiand she previously guessed some j>ij > i such that Bessie responded with "LO!,"Elsie will not guess ii and will move on to the next number in the list. It canbe proven that using this strategy, Elsie always uniquely determines xxregardless of the permutation she creates.

If we concatenate all of Bessie's responses of either "HI" or "LO" into a singlestring S,S, the number of times Bessie says "HILO" is the number of length 44 substrings of SS that are equal to "HILO."

Bessie knows that Elsie will use this strategy and has already chosen the valueof xx, but she does not know what permutation Elsie will use. Your goal is tocompute the sum of the number of times Bessie says "HILO" over all permutationsthat Elsie could possibly choose, modulo 109+710^9+7.

  • 1N50001\le N\le 5000

Input Format

The only line of input contains NN and xx.

Output Format

The total number of HILOs modulo 109+710^9+7.

4 2
4 2

In this test case, Bessie's number is 2.52.5.

For example, if Elsie's permutation is (4,1,3,2)(4,1,3,2), then Bessie will say"HILOHILO," for a total of two "HILO"s. As another example, if Elsie'spermutation is (3,1,2,4)(3,1,2,4), then Bessie will say "HILOLO," for a total of one"HILO."

60 10
60 10

Scoring

  • Test cases 3-10 satisfy $N\le 50$.
  • Test cases 11-18 satisfy $N\le 500$.
  • Test cases 19-26 satisfy no additional constraints.

Problem Credit

Problem credits: Richard Qi