AT_agc045_d [AGC045D] Lamps and Buttons

[problemUrl]: https://atcoder.jp/contests/agc045/tasks/agc045_d $ 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 $ で割ったあまりを求めてください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ A $

すぬけくんの勝率を $ w $ とした時，$ w\ \times\ N! $ を $ 10^9+7 $ で割ったあまりを出力せよ．

### 制約 - $ 2\ \leq\ N\ \leq\ 10^7 $ - $ 1\ \leq\ A\ \leq\ \min(N-1,5000) $ ### Sample Explanation 1 すぬけくんはまず，ボタン $ 1 $ を押します． ランプ $ 1 $ が消灯した場合はすぬけくんの負けです． そうでないときは，新しく点灯したランプに対応するボタンを押します． ここで残っていたランプが点灯すれば，すぬけくんの勝ちです． 逆に，ランプ $ 1 $ が消灯した場合，すぬけくんの負けです． このゲームの勝率は $ 1/3 $ なので，$ (1/3)\times\ 3!=2 $ を出力します．