Circular Mirror
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2000
Tags: binary search, combinatorics, geometry, math, two pointers

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 triangleFigure 2. an example of a correct colouringFigure 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$$$.

Input format:
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.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

Example input:
4 2
10 10 6 14

Example output:
10

Example input:
1 2
10

Example output:
2

Editorial:
Let's represent the mirror as a circle with $$$N$$$ points at the circumference. First, one should notice that a circumscribed triangle (triangle whose vertices lie on the circumference of a circle) is a right triangle if only if one side of the triangle is the diameter of the circle. That means, for a single colour, there exists a right triangle with this colour if and only if both of the following conditions are satisfied:
• There exists two diametrically opposite points with this colour.
• This colour occurs in $$$3$$$ or more points.
Let's call a pair of diametrically opposite points as a diameter pair. From the information above, we can see that if we colour the points in a diameter pair with the same colour, all other points must not have that colour. If that condition is satisfied for all diameter pairs, there cannot be a right triangle with the same colour.
Let's find the number of diameter pairs in the circle and the number of points that do not belong to a diameter pair. Let the two values be $$$cntPair$$$ and $$$cntAlone$$$. One can find $$$cntPair$$$ and $$$cntAlone$$$ with two pointers or binary search using the prefix sum of the array $$$D$$$.
To find the number of colouring configurations, we can iterate $$$i$$$ from $$$0$$$ to $$$\min(cntPair, M)$$$. In each iteration, we calculate the number of configurations that have exactly $$$i$$$ diameter pairs with the same colour on both of their points. It is calculated as follows:
• There are $$$\binom{cntPair}{i}$$$ ways to choose which diameter pairs have the same colour.
• Notice that each diameter pair with the same colour must have a different colour from each other. So there are $$$\binom{M}{i} \times i!$$$ ways to choose which colour is assigned to each diameter pair with the same colour.
• There are only $$$M-i$$$ available colours for colouring the remaining points. Each diameter pair with different colours can be coloured in $$$(M-i) \times (M-i-1)$$$ ways and each of the remaining points can be coloured in $$$M-i$$$ ways.
• So the total number of ways for a single value of $$$i$$$ is: $$$$$$\binom{cntPair}{i} \times \binom{M}{i} \times i! \times ((M-i) \times (M-i-1))^{cntPair-i} \times (M-i)^{cntAlone}$$$$$$
Time complexity: $$$O((N+M) \log N)$$$