Ay đang học phép thuật tại Đại học Phép thuật Ranoa!

Hôm nay, Ay đang học về các vòng tròn ma thuật. Vòng tròn ma thuật trước mặt Ay bao gồm một hình tròn và $n$ điểm ma thuật nằm trên đường tròn đó. $n$ điểm ma thuật này chia đường tròn thành $n$ phần bằng nhau, được đánh số theo chiều kim đồng hồ từ $1, 2, \dots, n$. Điểm ma thuật thứ $i$ có màu $c_i$ và giá trị ma lực $a_i$, trong đó $c_i \le k$. Nếu hai điểm ma thuật có cùng màu, chúng sẽ được nối với nhau bằng một đoạn thẳng ma thuật cùng màu, giá trị ma lực của đoạn thẳng này bằng tích giá trị ma lực của hai điểm ma thuật mà nó kết nối. Nếu hai đoạn thẳng ma thuật có màu khác nhau cắt nhau, chúng sẽ tạo ra một cường độ ma thuật bằng tích giá trị ma lực của hai đoạn thẳng đó. Cường độ ma thuật của toàn bộ vòng tròn ma thuật là tổng cường độ ma thuật tạo ra bởi mỗi cặp đoạn thẳng khác màu cắt nhau.

Hiện tại, Ay muốn biết giá trị cường độ ma thuật của vòng tròn ma thuật trước mặt mình. Vì kết quả có thể rất lớn, bạn chỉ cần đưa ra kết quả sau khi lấy mô-đun $998244353$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương $n, k$ ($4 \le n \le 5 \times 10^5, 2 \le k \le 100$), biểu thị số lượng điểm ma thuật và giới hạn số màu của các điểm ma thuật.

Dòng thứ hai chứa $n$ số nguyên dương, số nguyên thứ $i$ biểu thị màu $c_i$ của điểm ma thuật thứ $i$ ($1 \le c_i \le k$).

Dòng thứ ba chứa $n$ số nguyên dương, số nguyên thứ $i$ biểu thị giá trị ma lực $a_i$ của điểm ma thuật thứ $i$ ($0 \le a_i < 998244353$).

Dữ liệu ra

Một dòng chứa một số nguyên duy nhất, biểu thị giá trị cường độ ma thuật của vòng tròn ma thuật sau khi lấy mô-đun $998244353$.

Ví dụ

Ví dụ 1

4 2
1 2 1 2
1 2 3 4

Ví dụ 1

24

Ví dụ 2

8 4
1 4 2 2 1 2 4 2
3 1000 1 1000 4 2 1000 1000

Ví dụ 2

786705612