아야는 라노아 마법 대학에서 마법을 배우고 있습니다!

오늘 아야는 마법진에 관한 지식을 배우고 있습니다. 아야 앞에 있는 마법진은 하나의 원과 그 원 위의 $n$개의 마법 노드로 구성되어 있습니다. 이 $n$개의 마법 노드는 원을 $n$등분하며, 시계 방향으로 $1, 2, \dots, n$번까지 번호가 매겨져 있습니다. 번호가 $i$인 마법 노드는 색상 $c_i$와 마력 값 $a_i$를 가지며, 여기서 $c_i$의 크기는 $k$를 넘지 않습니다. 만약 두 마법 노드의 색상이 같다면, 이 두 노드는 같은 색상의 마법 선분으로 연결되며, 이 마법 선분의 마력 값은 연결된 두 마법 노드의 마력 값의 곱입니다. 만약 서로 다른 색상의 두 마법 선분이 교차한다면, 두 마법 선분의 마력 값의 곱에 해당하는 마법 강도가 발생합니다. 전체 마법진의 마법 강도는 교차하는 모든 서로 다른 색상의 선분 쌍에서 발생하는 마법 강도의 합입니다.

이제 아야는 자신 앞에 있는 마법진의 마법 강도 값을 알고 싶어 합니다. 정답이 매우 클 수 있으므로, 정답을 $998244353$으로 나눈 나머지를 출력하십시오.

입력

첫 번째 줄에는 두 개의 정수 $n, k$ ($4 \le n \le 5 \times 10^5, 2 \le k \le 100$)가 주어지며, 이는 마법 노드의 개수와 마법 노드 색상의 상한을 나타냅니다.

두 번째 줄에는 $n$개의 정수가 주어지며, $i$번째 정수는 번호가 $i$인 마법 노드의 색상 $c_i$ ($1 \le c_i \le k$)를 나타냅니다.

세 번째 줄에는 $n$개의 정수가 주어지며, $i$번째 정수는 번호가 $i$인 마법 노드의 마력 값 $a_i$ ($0 \le a_i < 998244353$)를 나타냅니다.

출력

한 줄에 하나의 정수를 출력하며, 이는 마법진의 마법 강도를 $998244353$으로 나눈 나머지를 나타냅니다.

예제

입력 1

4 2
1 2 1 2
1 2 3 4

출력 1

24

입력 2

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

출력 2

786705612