/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
1 から N までの番号のついた N 個のランプと，1 から N までの番号のついた N 個のボタンがあります． 最初，ランプ 1,2,\cdots,A は点灯しており，それ以外のランプは点灯していません．
すぬけくんとりんごさんは，次のようなゲームを行うことにしました．
-
まず，りんごさんが (1,2,\cdots,N) の順列 (p_1,p_2,\cdots,p_N) を生成する． この順列は N! 通りの中から一様ランダムに選ばれる． すぬけくんは，この順列を知らされない．
-
次に，すぬけくんは，以下の操作を好きなだけ繰り返す．
- 現在点灯しているランプを 1 つ選ぶ（そのようなランプがない場合は操作を行えない）． 選んだランプの番号を i とする． そして，ボタン i を押す． すると，ランプ p_i の状態が反転する．つまり，ランプ p_i がもともと点灯しているなら消灯し，もともと点灯していないなら点灯する．
すぬけくんは，常に，どのランプが点灯しているかを知ることができます． すぬけくんの勝利条件は，すべてのランプを点灯した状態にすることです． これが不可能と判明した時点ですぬけくんは負けを認めます． すぬけくんが最適に行動するとき，勝率はいくらでしょうか？
すぬけくんの勝率を w とした時，w \times N! は整数になります． w \times N! を 10^9+7 で割ったあまりを求めてください．
制約
- 2 \leq N \leq 10^7
- 1 \leq A \leq \min(N-1,5000)
入力
入力は以下の形式で標準入力から与えられる．
N A
出力
すぬけくんの勝率を w とした時，w \times N! を 10^9+7 で割ったあまりを出力せよ．
入力例 1
3 1
出力例 1
2
すぬけくんはまず，ボタン 1 を押します． ランプ 1 が消灯した場合はすぬけくんの負けです． そうでないときは，新しく点灯したランプに対応するボタンを押します． ここで残っていたランプが点灯すれば，すぬけくんの勝ちです． 逆に，ランプ 1 が消灯した場合，すぬけくんの負けです． このゲームの勝率は 1/3 なので，(1/3)\times 3!=2 を出力します．
入力例 2
3 2
出力例 2
3
入力例 3
8 4
出力例 3
16776
入力例 4
9999999 4999
出力例 4
90395416
Score : 1200 points
Problem Statement
We have N lamps numbered 1 to N, and N buttons numbered 1 to N. Initially, Lamp 1, 2, \cdots, A are on, and the other lamps are off.
Snuke and Ringo will play the following game.
-
First, Ringo generates a permutation (p_1,p_2,\cdots,p_N) of (1,2,\cdots,N). The permutation is chosen from all N! possible permutations with equal probability, without being informed to Snuke.
-
Then, Snuke does the following operation any number of times he likes:
- Choose a lamp that is on at the moment. (The operation cannot be done if there is no such lamp.) Let Lamp i be the chosen lamp. Press Button i, which switches the state of Lamp p_i. That is, Lamp p_i will be turned off if it is on, and vice versa.
At every moment, Snuke knows which lamps are on. Snuke wins if all the lamps are on, and he will surrender when it turns out that he cannot win. What is the probability of winning when Snuke plays optimally?
Let w be the probability of winning. Then, w \times N! will be an integer. Compute w \times N! modulo (10^9+7).
Constraints
- 2 \leq N \leq 10^7
- 1 \leq A \leq \min(N-1,5000)
Input
Input is given from Standard Input in the following format:
N A
Output
Print w \times N! modulo (10^9+7), where w is the probability of Snuke's winning.
Sample Input 1
3 1
Sample Output 1
2
First, Snuke will press Button 1. If Lamp 1 turns off, he loses. Otherwise, he will press the button that he can now press. If the remaining lamp turns on, he wins; if Lamp 1 turns off, he loses. The probability of winning in this game is 1/3, so we should print (1/3)\times 3!=2.
Sample Input 2
3 2
Sample Output 2
3
Sample Input 3
8 4
Sample Output 3
16776
Sample Input 4
9999999 4999
Sample Output 4
90395416