問題一覧 > 通常問題

No.1258 コインゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 145
作問者 : 👑 PCTprobabilityPCTprobability / テスター : nok0nok0
8 ProblemId : 5110 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-22 18:46:11

問題文

正整数 $N,M,X$ が与えられます。

PCT君はコインを $N$ 回投げます。この時表がちょうど $K$ 回出て、かつ $K\ \bmod\ 2 = X$ を満たす時 $M^K$ ポイント獲得できます。

この時コインの表裏の出方としてあり得るものは $2^N$ 通りありますが、その全ての出方に対して獲得できるポイントの合計を求めてください。

ただし答えは非常に大きくなることがあるので $1000000007$ で割った余りを出力してください。

$1$ 回の入力で $S$ 個のテストケースに答えてください。

入力

まずテストケースの個数 $S$ が与えられます。 
$S$
その後 $S$ 行に渡り $S$ 個のテストケースが与えられます。 
$N\ M\ X$

  • 入力は全て整数である。
  • $1 \le S \le 10^5$
  • $1 \le N,M \le 10^9$
  • $0 \le X \le 1$

出力

各テストケースでPCT君が獲得できるポイントの総数を出力してください。各テストケースごとに改行してください。

サンプル

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

PCT君はコインを $3$ 回投げて表が $K$ 回出たら $K$ が奇数の時に限り $2^K$ ポイントを獲得できます。

  • 表が $1$ 回でる投げ方は $3$ 通りなので $3×2^1=6$ ポイント
  • 表が $3$ 回でる投げ方は $1$ 通りなので $1×2^3=8$ ポイント
より $6+8=14$ を出力します。

サンプル2
入力
3
100 100 1
34 23 0
987 876 1
出力
906698789
801784688
310687510

$1000000007$ で割った余りを出力してください。

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