問題一覧 > 通常問題

No.1258 Coin Game

レベル : / AI推定難易度 : 850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 148
作問者 : PCTprobability / テスター : nok0
お気に入りにしたユーザー ProblemId : 5110 / 自分の提出
問題文最終更新日: 2021-03-22 18:46:11
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 270 (mathematics contest) (順位表) の他の問題:

Problem Statement

You are given positive integers $N,M,X$.

PCT-kun tosses a coin $N$ times. If heads comes up exactly $K$ times and $K\ \bmod\ 2 = X$ is satisfied, he earns $M^K$ points.

There are $2^N$ possible outcomes of heads and tails. Find the total of the points earned over all of these outcomes.

Since the answer can be very large, output it modulo $1000000007$.

Answer $S$ test cases in $1$ input.

Input

First, the number of test cases $S$ is given. 
$S$
Then, $S$ test cases are given over the following $S$ lines. 
$N\ M\ X$

  • All inputs are integers.
  • $1 \le S \le 10^5$
  • $1 \le N,M \le 10^9$
  • $0 \le X \le 1$

Output

For each test case, output the total number of points PCT-kun can earn. Print a newline after each test case.

Sample

Sample 1
Input
1
3 2 1
Output
14

PCT-kun tosses the coin $3$ times, and if heads comes up $K$ times, he earns $2^K$ points only when $K$ is odd.

  • Heads can come up $1$ time in $3$ ways, giving $3×2^1=6$ points
  • Heads can come up $3$ times in $1$ way, giving $1×2^3=8$ points
Therefore, output $6+8=14$.

Sample 2
Input
3
100 100 1
34 23 0
987 876 1
Output
906698789
801784688
310687510

Output the answer modulo $1000000007$.

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