Pak Chanek 有一面圆形镜子。圆周上有$$$N$$$个灯,按顺时针顺序从$$$1$$$到$$$N$$$编号。对于 $$$1 \leq i \leq N-1$$$,从灯 $$$i$$$ 到灯 $$$i+1$$$ 的弧长为 $$$D_i$$$。同时,灯$$$N$$$和灯$$$1$$$之间的弧长为$$$D_N$$$。
Pak Chanek 想要用 $$$M$$$ 不同的颜色给灯上色。每盏灯都可以使用 $$$M$$$ 颜色之一进行着色。但是,不可能存在三种不同的灯,使得这三个灯的颜色相同并且以这三个灯为顶点所构成的三角形是直角三角形(其中一个角恰好为$$$90$$$度的三角形)。
以下是圆形镜上灯着色配置的示例。
图 1. 错误着色的示例,因为灯 $$$1$$$、$$$2$$$ 和 $$$3$$$ 形成直角三角形图 2. 正确着色的示例图 3. 正确着色的示例
在给灯着色之前,Pak Chanek 想知道他可以制作多少种不同的着色配置。计算不同可能的灯着色配置的数量,以 $$$998\,244\,353$$$ 为模。
输入
第一行包含两个整数 $$$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$$$) — 镜子中灯之间的弧长。
输出
一个整数,表示可能的灯着色配置的数量,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
4 2 10 10 6 14
输出 #1
10
输入 #2
1 2 10
输出 #2
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]$$$。