Maximizing the Guessing Probability

docriz is taking an exam and encounters a strange multiple‐choice question at which he is completely clueless. The question has \(n\) options with exactly one correct answer. Since he doesn’t know the answer, he resorts to guessing.

The guessing process is done in \(n-2\) rounds. Before the rounds start (i.e. at round 0), docriz randomly picks one option among the \(n\) options. Then, for each round \(i\) from \(1\) to \(n-2\) the process is as follows:

1. Elimination: nocriz comes and eliminates one option. nocriz knows the correct answer so he will choose uniformly at random one option from the currently available options excluding the correct option and the option that docriz is currently holding. (Note: if docriz’s current selection is already the correct answer then the only option to exclude is that one option.)
2. Switching: After the elimination, docriz is allowed to either stick with his current option or switch. If he decides to switch, he will randomly pick one option from the remaining options except his current one.

However, due to a mysterious agreement with nocriz, docriz must switch his selection in exactly \(k\) out of the \(n-2\) rounds. In the rounds where he does not switch his choice remains unchanged.

It turns out that an optimal strategy exists. Roughly speaking, since switching when holding the correct answer is harmful (because switching from the correct option yields an certainly wrong option) while switching when holding a wrong answer gives a chance to win, the optimal strategy is to postpone any switches as late as possible so that they occur when docriz’s current option is wrong. More precisely, if we split the process into two segments:

• In the first \(n-2-k\) rounds, docriz does not switch so that his state (correct or wrong) remains unchanged.
• In the last \(k\) rounds (called the forced rounds) he must switch in every round. In these rounds, if his state is wrong then switching gives him a chance to recover the correct answer whereas if his state is correct switching will certainly lose the correct answer. However, if he recovers a correct answer in one forced round, a subsequent forced switch will ruin it. An analysis of the forced rounds yields the following recurrence: Let \(F(m,0)\) be the probability of ending up correct after \(m\) forced rounds starting from a wrong state and \(F(m,1)\) be that probability starting from a correct state. The recurrences are</p>

  [ \begin{aligned} F(0,0)&=0, \quad F(0,1)=1,\[1mm] F(m,1)&=F(m-1,0),\[1mm] F(m,0)&=\frac{1}{m} F(m-1,1) + \frac{m-1}{m}F(m-1,0) \quad (m\ge1). \end{aligned} ]

  Thus, the overall probability of ending up correct is:

  [ \text{ans} = \begin{cases} \frac{1}{n}, & \text{if } k=0,\[1mm] \frac{F(k,1) + (n-1),F(k,0)}{n}, & \text{if } k \ge 1. \end{cases} ]

  Since the answer is a rational number, you are to output it in its fractional form modulo \(10^9+7\); that is, if the answer is \(\frac{p}{q}\) (in reduced form) then output \(p\,q^{-1}\bmod (10^9+7)\).

  Input Format:

  • The input consists of two space‐separated integers \(n\) and \(k\) (with \(n\ge 3\) and \(0\le k\le n-2\)).

  Output Format:

  • Output a single integer which is the value of the maximum winning probability in modulo \(10^9+7\) (i.e. the fraction \(\frac{p}{q}\) modulo \(10^9+7\)).

  Example:

  Input: 4 1
  Output: 750000006
  

  Explanation: For \(n=4\) and \(k=1\) the optimal strategy is to never switch in the first \(n-2-1 = 1\) round and then switch in the last round. In this case, if docriz initially picks the wrong option (which happens with probability \(\frac{3}{4}\)) then in the final round switching when two options remain will guarantee a win. Thus, the overall winning probability is \(\frac{3}{4}\). The output is the value of \(\frac{3}{4}\) modulo \(10^9+7\).

  inputFormat

  The input consists of a single line containing two space‐separated integers (n) and (k).

  outputFormat

  Output a single integer representing the maximum probability (in fraction form modulo (10^9+7)).

  sample

  4 1

  750000006