問題一覧 > 通常問題

No.474 Coloring 2

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 33
作問者 : snuke / テスター : tanzaku
お気に入りにしたユーザー ProblemId : 1355 / 自分の提出
問題文最終更新日: 2026-06-25 19:25:56
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
Advent Calendar Contest 2016 (順位表) の他の問題:

Problem Statement

There is a rooted tree as described below.

  • The root has $A$ children.
  • Each of the $A$ children of the root has $B$ leaves attached to it.
Find the number of ways to color the vertices of this rooted tree with $C$ colors, mod 2. Here, colorings that can be made to coincide by reordering children are considered the same coloring.

For example, when $A=3,\ B=2$, the rooted tree is as shown in the figure below.

Then, for example, the $3$ colorings in the figure below are all considered the same.

Input

$T$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$:$
$A_T$ $B_T$ $C_T$

  • $T\ (1 \leq T \leq 10^5)$ is the number of test cases.
  • $A_i,B_i,C_i\ (1 \leq A_i,B_i,C_i \leq 10^6)$ are the values described in the problem statement.

Output

For each test case, print the answer on $1$ line. Print a newline at the end.

Sample

Sample 1
Input
4
2 2 2
1 1 999999
1000000 1000000 1
31415 9265 35897
Output
0
1
1
0

The number of colorings is $42$ for test case $1$, $999999^3$ for test case $2$, and $1$ for test case $3$.

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