Dịch đáp án

Bạn phải làm một bài kiểm tra gồm $n$ câu hỏi trắc nghiệm. Mỗi câu có $k$ phương án và chỉ một phương án đúng. Đáp án đúng của câu thứ $i$ là $h_i$. Nếu bạn trả lời câu $i$ bằng đúng $h_i$ thì được $1$ điểm cho câu đó, ngược lại được $0$ điểm.

Bạn dự định điền một bộ đáp án $a=[a_1,a_2,\dots ,a_n]$ (với $1\le a_i\le k$). Tuy nhiên, do một lỗi trong chương trình, các đáp án bị dịch vòng theo chiều kim đồng hồ đúng một vị trí trước khi nộp: đáp án của câu $i$ bị chuyển sang câu $imodn+1$. Nghĩa là bộ đáp án thực sự được nộp là $a^{\prime }=[a_n,a_1,a_2,\dots ,a_{n-1}]$.

Gọi tổng điểm của bộ đáp án gốc $a$ là số câu $i$ mà $a_i=h_i$, và tổng điểm của bộ bị dịch $a^{\prime }$ là số câu $i$ mà $a_i^{\prime }=h_i$.

Có tất cả $k^n$ bộ đáp án khả dĩ. Hãy đếm số bộ đáp án $a$ sao cho tổng điểm của $a^{\prime }$ (sau khi dịch) lớn hơn thực sự tổng điểm của $a$ (ban đầu). In kết quả theo modulo $998244353$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$: số câu hỏi và số phương án mỗi câu.
• Dòng thứ hai chứa $n$ số nguyên $h_1,h_2,\dots ,h_n$: đáp án đúng của từng câu.

Dữ liệu ra

• In một số nguyên: số bộ đáp án thỏa mãn điều kiện, theo modulo $998244353$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le k\le {10}^9$
• $1\le h_i\le k$

Ví dụ