No.474 色塗り2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 22
作問者 : snukesnuke / テスター : tanzakutanzaku

4 ProblemId : 1355 / 出題時の順位表

問題文

以下のような根付き木があります。

  • 根に $A$ 個の子がついている。
  • 根の $A$ 個の子にそれぞれ $B$ 個ずつ葉がついている。
この根付き木の頂点を $C$ 色で塗り分ける場合の数をmod 2で求めてください。 ただし、子の順番を並び替えることで一致するような塗り方は同じ塗り方であるとします。

例えば、$A=3,\ B=2$ の場合は下図のような根付き木となります。

そして、例えば下図の $3$ つの塗り方は全て同じと見なされます。

入力

$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)$ はテストケース数を表す。
  • $A_i,B_i,C_i\ (1 \leq A_i,B_i,C_i \leq 10^6)$ は問題文中で示した通りの値である。

出力

各テストケースに対する答えを $1$ 行ずつ出力してください。 最後に改行してください。

サンプル

サンプル1
入力
4
2 2 2
1 1 999999
1000000 1000000 1
31415 9265 35897
出力
0
1
1
0

$1$ ケース目の塗り方は $42$ 通り、$2$ ケース目の塗り方は $999999^3$ 通り、$3$ ケース目の塗り方は $1$ 通りです。

提出ページヘ