CF1725C.Circular Mirror

Pak Chanek has a mirror in the shape of a circle. There are $N$ lamps on the circumference numbered from $1$ to $N$ in clockwise order. The length of the arc from lamp $i$ to lamp $i+1$ is $D_i$ for $1 \leq i \leq N-1$. Meanwhile, the length of the arc between lamp $N$ and lamp $1$ is $D_N$.

Pak Chanek wants to colour the lamps with $M$ different colours. Each lamp can be coloured with one of the $M$ colours. However, there cannot be three different lamps such that the colours of the three lamps are the same and the triangle made by considering the three lamps as vertices is a right triangle (triangle with one of its angles being exactly $90$ degrees).

The following are examples of lamp colouring configurations on the circular mirror.

Figure 1. an example of an incorrect colouring because lamps $1$, $2$, and $3$ form a right triangle

Figure 2. an example of a correct colouring

Figure 3. an example of a correct colouring

Before colouring the lamps, Pak Chanek wants to know the number of distinct colouring configurations he can make. Count the number of distinct possible lamp colouring configurations, modulo $998\,244\,353$.

帕克·查内克有一面圆形的镜子。在圆周上按顺时针顺序编号有 $N$ 盏灯，编号从 $1$ 到 $N$。灯 $i$ 到灯 $i+1$ 之间的圆弧长度为 $D_i$（其中 $1 \leq i \leq N-1$）；而灯 $N$ 与灯 $1$ 之间的圆弧长度为 $D_N$。

帕克·查内克希望用 $M$ 种不同颜色为这些灯染色。每盏灯可被染成 $M$ 种颜色中的任意一种。但不允许存在三盏互不相同的灯，使得这三盏灯颜色相同，且以这三盏灯为顶点构成的三角形是直角三角形（即其中一个内角恰好为 $90^\circ$）。

以下是圆形镜子上灯染色方案的一些示例：

图 1：一种错误的染色方案，因为灯 $1$、$2$、$3$ 构成一个直角三角形

图 2：一种正确的染色方案

图 3：一种正确的染色方案

在给灯染色之前，帕克·查内克想知道他能构造出多少种不同的染色方案。请计算所有可能的灯染色方案总数，对 $998\,244\,353$ 取模。

The first line contains two integers $N$ and $M$ ($1 \le N \le 3 \cdot 10^5$, $2 \le M \le 3 \cdot 10^5$) — the number of lamps in the mirror and the number of different colours used.

The second line contains $N$ integers $D_1, D_2, \ldots, D_N$ ($1 \le D_i \le 10^9$) — the lengths of the arcs between the lamps in the mirror.

第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 3 \cdot 10^5$，$2 \le M \le 3 \cdot 10^5$）—— 分别表示镜中灯的数量以及所使用的不同颜色的数量。

第二行包含 $N$ 个整数 $D_1, D_2, \ldots, D_N$（$1 \le D_i \le 10^9$）—— 表示镜中各灯之间弧段的长度。

An integer representing the number of possible lamp colouring configurations, modulo $998\,244\,353$.

一个整数，表示可能的灯颜色配置方案数对 $998\,244\,353$ 取模的结果。

In the first example, all correct lamp colouring configurations are $[1, 1, 2, 1]$, $[1, 1, 2, 2]$, $[1, 2, 1, 2]$, $[1, 2, 2, 1]$, $[1, 2, 2, 2]$, $[2, 1, 1, 1]$, $[2, 1, 1, 2]$, $[2, 1, 2, 1]$, $[2, 2, 1, 1]$, and $[2, 2, 1, 2]$.

在第一个例子中，所有正确的灯颜色配置为 $[1, 1, 2, 1]$、$[1, 1, 2, 2]$、$[1, 2, 1, 2]$、$[1, 2, 2, 1]$、$[1, 2, 2, 2]$、$[2, 1, 1, 1]$、$[2, 1, 1, 2]$、$[2, 1, 2, 1]$、$[2, 2, 1, 1]$ 和 $[2, 2, 1, 2]$。