問題一覧 > 通常問題

No.2264 Gear Coloring

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : sotanishysotanishy / テスター : karinohitokarinohito
2 ProblemId : 9329 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-06 23:57:58

問題文

$N$ 個の歯車があり,$i$ 個目の歯車には $A_i$ 個の歯がついています.$i=1,2,\dots,N-1$ について,歯車 $i$ と歯車 $i+1$ は噛み合っており,歯車 $i$ が歯 1 個分回転すると,歯車 $i+1$ も連動して歯 1 個分回転します.

これから,$M$ 色を使ってそれぞれの歯車のそれぞれの歯を塗ります.回転によって一致する色の塗り方を同一視するとき,色の塗り方は何通りありますか.$998244353$ で割った余りを求めてください.

入力

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$

  • $2 \leq N \leq 1000$
  • $1 \leq M \lt 998244353$
  • $3 \leq A_i \lt 998244353$
  • $\mathrm{lcm}(A_1,A_2,\dots,A_N) \lt 998244353$
  • 入力はすべて整数

出力

答えを $998244353$ で割った余りを出力してください. 最後に改行してください。

サンプル

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

サンプル2
入力
2 3
3 4
出力
264

サンプル3
入力
3 4
3 5 7
出力
11701248

サンプル4
入力
4 100
10 1000 100000 100000000
出力
827082837

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

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