No.391 CODING WAR
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 218
作問者 :
Tawara
/ テスター :
37zigen
タグ : / 解いたユーザー数 218
作問者 :
Tawara
/ テスター :
37zigen
問題文最終更新日: 2016-07-08 22:54:47
問題文
yuki王国の存在する競プロ大陸では、国家間で揉め事が起きるとCODING WARで決着をつけます。
CODING WARとは、攻撃側の国が出題した問題に守備側の国の競技プログラマ全員で挑む戦いです。
ただし一部の本当に強い競技プログラマ、いわゆるプロが全部の問題を解いてしまうと、
国家全体の競技プログラマ力で勝負したとはいえません。
そこで、CODING WARでは以下のルールに従って問題の担当者を決めます。
- 守備側の競技プログラマ全員がいずれかの問題に取り組まなければならない。
- 出題された各問題には必ず取り組む（担当する）人が存在しなければならない。
- 各プログラマの担当する問題は一つに限り、自分の担当でない問題に取り組む人に助言を行ってはならない。
- 同じ問題を担当するプログラマが複数いても良い。
さて、今日も作問した問題の著作権を巡って隣国がyuki王国にCODING WARを仕掛けて来たようです。
ところがYuki王国のCODING大臣は就任したばかりで勝手が分かっていません。秘書の貴方に対し、
問題の担当者の決め方を全部列挙してからそれを眺めて担当者の決定を行うなんて戯け..ｺﾞﾎﾝ、御冗談をおっしゃいました。
問題の担当者の決め方が全部で何通りかを大臣にお教えし、現実というものを思い知らせて下さい。
2016/07/08 22:54 追記:
攻撃側の反則負けになる場合は0通りであるとする。
入力
$N$ $M$
一行目にyuki王国の競技プログラマ人口 $N$ ($1 \le N \le 10^{12}$)、 隣国の出題した問題数 $M$ ($1 \le M \le 10^5 $) が空白区切りで与えられます。
出力
問題の担当者の決め方が何通りか答えて下さい。
ただし、答えが非常に大きくなる場合があるため $1000000007(10^9+7)$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 3
出力
6
yuki王国の三人の競技プログラマそれぞれが担当する問題の番号を$a,b,c$とすると
$(a,b,c)=(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$
の6通りが存在します。
サンプル2
入力
7 3
出力
1806
同じ問題の担当者が複数居るようなケースです。
サンプル3
入力
100 1
出力
1
yuki王国の競技プログラマの総力を結集して一つの問題に挑みます。
サンプル4
入力
1000000000000 3
出力
692089859
yuki王国には凄まじい数の競技プログラマがいるようです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。