問題一覧 > 通常問題

No.2264 Gear Coloring

レベル : / AI推定難易度 : 2025 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 43
作問者 : sotanishy / テスター : karinohito
お気に入りにしたユーザー ProblemId : 9329 / 自分の提出
問題文最終更新日: 2026-05-29 18:57:38
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 383 (順位表) の他の問題:

Problem Statement

There are $N$ gears, and the $i$-th gear has $A_i$ teeth. For $i=1,2,\dots,N-1$, gear $i$ and gear $i+1$ are meshed: when gear $i$ rotates by 1 tooth, gear $i+1$ also rotates by 1 tooth along with it.

You will now paint each tooth of each gear using $M$ colors. Two colorings are considered the same if they coincide after a rotation. How many colorings are there? Find the count modulo $998244353$.

Input

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

  • $2 \leq N \leq 1000$
  • $1 \leq M$$ \le 10^9$ (Updated 2026/05/29)
  • $3 \leq A_i \lt 998244353$
  • $\mathrm{lcm}(A_1,A_2,\dots,A_N) \lt 998244353$
  • All inputs are integers.

Output

Output the answer modulo $998244353$. Print a newline at the end.

Sample

Sample 1
Input
2 2
3 3
Output
24

Sample 2
Input
2 3
3 4
Output
264

Sample 3
Input
3 4
3 5 7
Output
11701248

Sample 4
Input
4 100
10 1000 100000 100000000
Output
827082837

Output the answer modulo $998244353$.

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