問題一覧 > 通常問題

No.1704 Many Bus Stops (easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 75
作問者 : harurunharurun / テスター : chineristACchineristAC
1 ProblemId : 6985 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-09 00:46:08

問題文

A,B,Cの $3$ つのバス停があります。

時刻 $0$ にバス停Aにバスが $1$ 台止まっていて、バス停A以外にはバスがいません。

時刻 $i=0,1,2,...,N-1$ に各バス停にいるバスはそれぞれ以下のように動きます。

  • バス停Aにバスがいる場合

    • 確率 $\frac{1}{3}$ でバス停Bに時間 $1.5$ かけて移動する

    • 確率 $\frac{1}{3}$ でバス停Cに 時間 $1.5$ かけて移動する

    • 確率 $\frac{1}{3}$ でバス停Aにとどまる

  • バス停Bにバスがいる場合

    • 確率 $\frac{1}{3}$ でバス停Cに時間 $1.5$ かけて移動する

    • 確率 $\frac{1}{3}$ でバス停Aに時間 $1.5$ かけて移動する

    • 確率 $\frac{1}{3}$ でバス停Bにとどまる

  • バス停Cにバスがいる場合

    • 確率 $\frac{1}{3}$ でバス停Aに時間 $1.5$ かけて移動する

    • 確率 $\frac{1}{3}$ でバス停Bに時間 $1.5$ かけて移動する

    • 確率 $\frac{1}{3}$ でバス停Cにとどまる

時刻 $N$ にバス停Aにバスが1台以上いる確率を $\mod 10^9+7$ で出力してください。

$T$ 個のテストケースに答えてください。


確率を $\mod 10^9+7$ で出力するとは (クリックで開きます)

確率を既約分数 $\frac{P}{Q}$ で表したとき、 $R\times Q=P (mod 10^9+7)$ を満たし、かつ $0≤R<10^9+7$ を満たす 非負整数 $R$ を出力してください。

入力

$T$

1行目にはテストケースの数 $T$ が与えられる。

各テストケースは以下のようになっており、$T$ 行与えられる。

$N$

整数 $N$ が与えられる。

制約

  • $1≤T≤3\times10^3$

  • $1≤N≤1\times10^9$

  • 入力は全て整数である

サンプル

サンプル1
入力
5
3
5
10
100
1000000000
出力
370370373
930041159
79120731
511323553
802083332

テストケース $1$ について、 答えの確率は $\frac{1}{27}$ です。 $\mod 10^9+7$ の $370370373$ を出力してください。

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