K. Unique Disk Identifier
time limit per test
2.5 seconds
memory limit per test
768 megabytes
input
standard input
output
standard output

Iceberg Corporation has made many breakthroughs in many areas, such as cryptography and artificial intelligence, where they were able to register many patents.

One of them is a powerful automated personnel identification system that does not suffer from any practical security exploits. It was carefully designed by its prominent engineers: Yessine, Rami, and Oussama. This system identifies each person with his unique disk.

In fact, each disk is composed of $$$n$$$ sectors, where the $$$i^\text{th}$$$ sector is divided into $$$A_i$$$ isometric chunks. Each chunk has its own color from a list of $$$K$$$ available colors.

To have login access, each person will insert his disk into a disk scanner that identifies the person and gives or denies him access. The scanner is smart enough to detect a flipped disk and correctly realign any sector by rotating it.

The security of this system relies heavily on the number of different configurations of disks. Calculate the number of different disk configurations. As the number can be very big, you only have to calculate it modulo $$$M=998244353.$$$

Two configurations are equivalent if you can get one from the other by rotating each sector by any angle and flipping the whole disk around any axis any number of times.

Input
  • The first line contains two integers $$$1\le n\le 10^5$$$ and $$$1\le K \le 10^9$$$ representing respectively the number of sectors and the number of colors.
  • The second line contains $$$n$$$ integers $$$1\le A_1,\dots,A_n\le 5\times 10^5$$$ representing the number of chunks for each sector.
Output

One integer $$$R,$$$ equal to the number of distinct colorings modulo $$$M=998244353$$$

Examples
Input
4 3
3 4 2 1
Output
3834
Input
2 2
4 2
Output
18
Note

The first test case corresponds to a system designed as follows:

  • The system supports $$$K=3$$$ available colors.
  • The disk is composed of $$$4$$$ sectors
  • $$$A=[3,4,2,1]$$$ is the array of chunks, starting from the innermost sector.
The example above corresponds to five configurations of the same disk. In the system, they will be detected by the scanner as the same disk. It can be shown that there are $$$3834$$$ distinct disks in total.

For the second test case, we can enumerate all distinct disks as follows: