問題一覧 > 通常問題

No.1728 [Cherry 3rd Tune] Bullet

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : 👑 KazunKazun / テスター : tatyamtatyam chocoruskchocorusk
4 ProblemId : 6353 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-08 21:12:46

お知らせ (2022/07/08 追記)

この問題は 2021 年 10 月 29 日に開催されたコンテストで出題された問題です.

問題文

$\mathcal{G}1$ と $\mathcal{G}2$ はほとんど同じ問題だが, 制約と実行時間制限が異なる.

チェリーちゃんは今回のコンテストの開催を記念して, 以下を満たすようなオブジェを作ることになった.

  • $\Gamma_N$ は以下を満たすような正 $N$ 角柱である.
    • 底面は1辺の長さが $1$ の正 $N$ 角形である.
    • 側面のうち, 2つの底面の頂点同士を結ぶ辺の長さはすべて $2$ である.
    • 全ての側面は底面と直交している.
  • $\Gamma_N$ にある $2N$ 個の頂点それぞれについて, 色 $1, \dots,$ 色 $C$ の計 $C$ 色の中から $1$ 色を選んで塗る.

ただし, 既にあるオブジェと似ているオブジェを作ってしまうと, SNS で炎上してしまう. また, 今はそうでなくても, 後々似たものが出てきても流れ弾を喰らって面倒くさいことになってしまう. このことを懸念したチェリーちゃんは上のような条件下でどのくらいオブジェクトを作ることができるかが気になった. そこで, $N, C$ が与えられるので, 以下の問題の答えを求めよ.

  • $\Gamma_N$ にある $2N$ 個の頂点の彩色で, 回転によって一致する場合を区別しない場合の彩色の方法は何通りか? $10^9+7$ で割った余りを出力せよ.

$T$ 個のテストケースについて答えよ.

制約

  • $1 \leq T \leq 10$
  • $3 \leq N \leq 10^9$
  • $1 \leq C \leq 10^9$
  • 入力は整数である.

入力

入力は標準入力から与えられる. 入力の $1$ 行目は以下の形式である.

$T$
その後, $T$ 個のテストケースが続く. 各テストケースは以下の形式で与えられる.
$N$ $C$

出力

出力は全部で $T$ 行からなる. 第 $t~(1 \leq t \leq T)$ 行目には, 第 $t$ テストケースでの $\Gamma_N$ にある $2N$ 個の頂点の彩色で, 回転によって一致する場合を区別しない場合の彩色の方法の数を $10^9+7$ で割った余りを出力せよ.

ただし, 改行を忘れないこと.

サンプル

サンプル1
入力
3
3 2
5 1
46 20211031
出力
16
1
173884620

  • [第1テストケースについて] 色 $1$ を赤, 色 $2$ を青とした場合, 以下の16通りの塗り方がある.
  • [第2テストケースについて] 1色でしか塗れないので, 全ての頂点をその色で塗る1通りだけである.
  • [第3テストケースについて] $10^9+7$ で割った余りを求めることに注意すること ($\mathcal{G}1$ 問題との違いである).

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