問題一覧 > 通常問題

No.1704 Many Bus Stops (easy)

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 101
作問者 : harurun / テスター : chineristAC
お気に入りにしたユーザー ProblemId : 6985 / 自分の提出
問題文最終更新日: 2021-10-09 00:46:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 317 (順位表) の他の問題:

Problem Statement

There are $3$ bus stops: A, B, and C.

At time $0$, $1$ bus is stopped at bus stop A, and there are no buses anywhere other than bus stop A.

At each time $i=0,1,2,...,N-1$, each bus at each bus stop moves as follows.

  • If a bus is at bus stop A:

    • with probability $\frac{1}{3}$, it moves to bus stop B, taking time $1.5$

    • with probability $\frac{1}{3}$, it moves to bus stop C, taking time $1.5$

    • with probability $\frac{1}{3}$, it stays at bus stop A

  • If a bus is at bus stop B:

    • with probability $\frac{1}{3}$, it moves to bus stop C, taking time $1.5$

    • with probability $\frac{1}{3}$, it moves to bus stop A, taking time $1.5$

    • with probability $\frac{1}{3}$, it stays at bus stop B

  • If a bus is at bus stop C:

    • with probability $\frac{1}{3}$, it moves to bus stop A, taking time $1.5$

    • with probability $\frac{1}{3}$, it moves to bus stop B, taking time $1.5$

    • with probability $\frac{1}{3}$, it stays at bus stop C

Output the probability that at least 1 bus is at bus stop A at time $N$, modulo $\mod 10^9+7$.

Answer $T$ test cases.


What it means to output a probability modulo $\mod 10^9+7$ (click to expand)

When the probability is expressed as an irreducible fraction $\frac{P}{Q}$, output the non-negative integer $R$ satisfying $R\times Q=P (mod 10^9+7)$ and $0≤R<10^9+7$.

Input

$T$

The first line contains the number of test cases $T$.

Each test case is as follows, and $T$ lines are given.

$N$

An integer $N$ is given.

Constraints

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

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

  • All input values are integers.

Sample

Sample 1
Input
5
3
5
10
100
1000000000
Output
370370373
930041159
79120731
511323553
802083332

For test case $1$, the probability of the answer is $\frac{1}{27}$. Output $370370373$, which is its value modulo $\mod 10^9+7$.

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