No.1706 Many Bus Stops (hard)
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 82
作問者 :
harurun
/ テスター :
chineristAC
タグ : / 解いたユーザー数 82
作問者 :
harurun
/ テスター :
chineristAC
問題文最終更新日: 2021-10-09 00:47:13
問題文
$C$ 個のバス停があり、それぞれバス停 $1$ 、バス停 $2$ 、....、バス停 $C$ と呼ぶことにします,
時刻 $0$ にバス停 $1$ にバスが $M$ 台止まっていて、バス停 $1$ 以外にはバスがいません。
時刻 $i=0,1,2,...,N-1$ に各バス停にいるすべてのバスはそれぞれ以下のように独立に動きます。
バス停 $x$ にバスがいる場合
バス停 $x$ 以外のバス停に、それぞれ確率 $\frac{1}{C}$ で時間 $1.5$ かけて移動する
確率 $\frac{1}{C}$ でバス停 $x$ にとどまる
時刻 $N$ にバス停 $1$ にバスが1台以上いる確率を $\mod 10^9+7$ で出力してください。
確率を $\mod 10^9+7$ で出力するとは (クリックで開きます)
確率を既約分数 $\frac{P}{Q}$ で表したとき、 $R\times Q=P (mod 10^9+7)$ を満たし、かつ $0≤R<10^9+7$ を満たす 非負整数 $R$ を出力してください。
入力
$C\ N\ M$
バス停の数 $C$ と整数 $N$ とバスの数 $M$ が空白区切りで与えられる。
制約
$2≤C≤1\times10^5$
$1≤N≤1\times10^9$
$1≤M≤1\times10^9$
入力は全て整数である
サンプル
サンプル1
入力
3 3 1
出力
370370373
答えの確率は $\frac{1}{27}$ です。 $\mod 10^9+7$ で出力してください。
サンプル2
入力
10 1 2
出力
830000006
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。