Chỉ số đa dạng

Trong một cuộc khảo sát môi trường, một nhóm các nhà sinh thái học đang nghiên cứu một hệ sinh thái tuyến tính, bao gồm \(n\) khu vực liên tiếp được đánh số từ \(1\) đến \(n\). Theo các nghiên cứu trước đó, có tổng cộng \(m\) loài sinh vật khác nhau được đánh số từ \(1\) tới \(m\). Các nhà khoa học đã ghi nhận mỗi khu vực \(i\) chỉ có một loài sinh vật đặc trưng là \(a_i\).

Để đánh giá sự đa dạng sinh học, các nhà khoa học đã chọn một đoạn khảo sát liên tiếp, từ khu vực \(l\) đến khu vực \(r\).

Một chỉ số được gọi là "chỉ số thiếu hụt đa dạng" được định nghĩa cho mỗi đoạn khảo sát \((l, r)\) như sau:

• Giả sử sau khi thống kê các loài sinh vật từ khu vực \(l\) đến \(r\), có \(k\) loài chưa được ghi nhận, lần lượt là \(c_1, c_2, \ldots, c_k\).
• "Chỉ số thiếu hụt đa dạng" sẽ bằng với tổng của các chỉ số loài này: \(c_1 + c_2 + \ldots + c_k\).

Để đưa ra báo cáo tổng quan về hệ sinh thái này, các nhà khoa học cần tính tổng "chỉ số thiếu hụt đa dạng" của tất cả các đoạn khảo sát liên tiếp \((x, y)\) với \(1 \le x \le y \le n\).

Yêu cầu: Cho trước \(n, m\) và mảng \(a\). Hãy tính tổng "chỉ số thiếu hụt đa dạng" của tất cả các đoạn khảo sát liên tiếp.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 2 \times 10^5, 1 \le m \le 10^9\)) lần lượt là số khu vực và số loại sinh vật.
• Dòng thứ hai chứa \(n\) số \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le m\)) là loại sinh vật đặc trưng ở mỗi khu vực.
• Lưu ý rằng có thể có các khu vực khác nhau cùng có một loại sinh vật, hoặc có loại không có khu vực nào.

Output

• In ra tổng "chỉ số thiếu hụt đa dạng" của mọi đoạn. Vì kết quả có thể rất lớn, hãy in ra sau khi chia lấy dư cho \(998244353\).

Example

3 4
1 2 3

40

8 4
2 3 1 2 4 3 1 3

124

Scoring

• Subtask 1 (20% số điểm): \(1 \le n, m \le 50\).
• Subtask 2 (20% số điểm): \(1 \le n, m \le 500\).
• Subtask 3 (20% số điểm): \(1 \le n, m \le 5000\).
• Subtask 4 (20% số điểm): \(m = 2\).
• Subtask 5 (20% số điểm): không có ràng buộc gì thêm.