Summing HILO Transitions

Bessie has chosen a number of the form \(x+0.5\) where \(x\) is an integer between \(0\) and \(N\) (with \(1 \le N \le 5000\)). Elsie is trying to guess that number. She first generates a permutation of the integers \(1,2,\dots,N\) (each number appears exactly once) and then, in that order, makes guesses. When Elsie is about to guess an integer \(i\), she skips it if a previous guess already gives enough information:

• If there is a previous guess \(j<i\) that produced the answer HI! (which means \(j> x+0.5\)), then Elsie does not guess \(i\) because she already knows that any later guess will also be too high.
• If there is a previous guess \(j>i\) that produced the answer LO! (which means \(j< x+0.5\)), then she skips \(i\) as well.

When Elsie does make a guess \(i\), Bessie replies as follows:

• If \(i > x+0.5\) (note that \(i\) is an integer and \(x+0.5\) is half‐integer) then the response is HI!.
• If \(i < x+0.5\) then the response is LO!.

It can be proved that by following this strategy, no matter what permutation Elsie uses, she can determine \(x\) uniquely. Now, if we concatenate all of Bessie's responses (removing the exclamation marks) into a string \(S\) (each guess contributes either the two‐letter string HI or LO), we define the HILO count to be the number of contiguous substrings of length 4 in \(S\) that equal HILO. In other words, an occurrence of the pattern HILO arises whenever an answer of HI is immediately followed by an answer of LO in the recorded guesses (note that overlapping occurrences are counted separately).

Bessie has fixed \(x\) but does not know which permutation Elsie will use. Your task is to compute, over all possible permutations that Elsie might choose, the sum of the HILO counts and output the answer modulo \(10^9+7\>.

---

Important observations and hints:

• The number \(x+0.5\) splits the numbers \(1,2,\dots,N\) into two groups. All numbers \(\le x\) will yield the answer LO! and all numbers \(\ge x+1\) will yield HI!.
• However, due to Elsie’s rule of skipping unnecessary guesses, not every number is actually guessed. In fact, within each group the only guesses that are made are those that form a record: in the lower group (\(\le x\)) only those numbers that are a new maximum (record high) are guessed, and in the higher group (\(\ge x+1\)) only those that are a new minimum (record low) are guessed.
• With this in mind the final record sequence is obtained by merging two sequences:
  • An increasing sequence from the lower group (all yielding LO),
  • A decreasing sequence from the higher group (all yielding HI).
• The only way to get the substring HILO in \(S\) is when a HI (from the high group) is immediately followed by a LO (from the low group) in the merged record sequence.
• A careful combinatorial/analytic argument shows that if the two groups have sizes \(A = N-x\) and \(B = x\), and if their record counts are denoted by \(a\) and \(b\) respectively, then for any fixed permutation the number of transitions HI followed immediately by LO is exactly \(\frac{a\,b}{a+b}\) (when \(a+b \ge 1\)). Since the record counts in a random permutation are classical combinatorial quantities, one may show that the sum of HILO counts over all \(N!\) permutations equals \[ N! \cdot E\Bigl[\frac{a\,b}{a+b}\Bigr]\mod (10^9+7). \]
• A standard method using the generating function of the unsigned Stirling numbers of the first kind leads to the identities \[ \sum_{r=1}^{m} r\,S(m,r)= m!\,H_m, \] where \(H_m\) is the \(m\)th harmonic number. Using an integration technique and exchanging sums one may reduce the problem to computing \[ E=\frac{1}{A!\,B!}\sum_{r=1}^{A}\;\sum_{s=1}^{B}\;\frac{r\,s}{r+s}\,S(A,r)\,S(B,s). \] You are free to use any method that gives the correct final answer modulo \(10^9+7\). (Note that if either \(A=0\) or \(B=0\) then no HILO occurs.)

Input Format:

The input consists of a single line containing two space‐separated integers \(N\) and \(x\) where \(0\le x\le N\) and \(1\le N\le 5000\).

Output Format:

Output a single integer: the sum of the HILO counts over all \(N!\) permutations, taken modulo \(10^9+7\).

inputFormat

The input consists of a single line with two integers \(N\) and \(x\) (with \(0\le x\le N\) and \(1\le N\le 5000\)).

Example:

5 3

outputFormat

Output one integer, the answer modulo \(10^9+7\).

For the sample input above, the output might be:

42

sample

4 2

0