[Solution] Circular Mirror Codeforces Solution

C. Circular Mirror

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Pak Chanek has a mirror in the shape of a circle. There are 𝑁$N$ lamps on the circumference numbered from 1$1$ to 𝑁$N$ in clockwise order. The length of the arc from lamp 𝑖$i$ to lamp 𝑖+1$i+1$ is 𝐷𝑖$D_i$ for 1≤𝑖≤𝑁−1$1\le i\le N-1$. Meanwhile, the length of the arc between lamp 𝑁$N$ and lamp 1$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$90$ degrees).

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

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 998244353$998244353$.

Input

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The second line contains 𝑁$N$ integers 𝐷1,𝐷2,…,𝐷𝑁$D_1,D_2,\dots ,D_N$ (1≤𝐷𝑖≤109$1\le D_i\le {10}^9$) — the lengths of the arcs between the lamps in the mirror.

Output

An integer representing the number of possible lamp colouring configurations, modulo 998244353$998244353$.

Note

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