No.1035 Color Box

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 164
作問者 : ningenMeningenMe / テスター : onakaT_TitaionakaT_Titai
6 ProblemId : 2772 / 出題時の順位表
問題文最終更新日: 2020-05-01 21:16:23

問題文

$1$から$N$までの異なる番号がそれぞれ書かれた$N$個の箱に$M$種類のペンキを使って色を塗ります。
このとき$M$種類全ての色を使う必要があり、また各箱は必ず何かの色で塗られるとします。
このとき色の塗り方の総数は何通りでしょうか?答えは非常に大きくなることがあるため$10^9+7$で割った余りで答えてください。

入力

$N\ M$

$1 \le M\le N \le 10^5$
与えられる入力は全て整数である。

出力

答えを1行で出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 2
出力
6

ペンキの色を$1$,$2$とし、3個の箱の色を($a$,$b$,$c$)で表すとすると、($a$,$b$,$c$)=($1$,$1$,$2$),($1$,$2$,$1$),($2$,$1$,$1$),($2$,$2$,$1$),($2$,$1$,$2$),($1$,$2$,$2$) の6種類の塗り方があります。

サンプル2
入力
4 4
出力
24

サンプル3
入力
100000 100000
出力
457992974

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。