¡Ayaka está estudiando magia en la Universidad de Magia de Ranoa!

Hoy, Ayaka está aprendiendo sobre círculos mágicos. El círculo mágico frente a ella consiste en un círculo y $n$ nodos mágicos situados sobre él. Estos $n$ nodos dividen el círculo en $n$ partes iguales y están numerados en orden horario del $1, 2, \dots, n$. El nodo mágico numerado con $i$ tiene un color $c_i$ y un valor de poder mágico $a_i$, donde $c_i \le k$. Si dos nodos mágicos tienen el mismo color, estarán conectados por un segmento de línea mágica del mismo color, y el valor de poder de este segmento será el producto de los valores de poder mágico de los dos nodos que conecta. Si dos segmentos de línea mágica de colores diferentes se cruzan, se genera una intensidad mágica igual al producto de los valores de poder de ambos segmentos. La intensidad mágica total del círculo mágico es la suma de las intensidades mágicas generadas por cada par de segmentos de colores diferentes que se cruzan.

Ahora, Ayaka quiere conocer el valor de la intensidad mágica del círculo mágico que tiene frente a ella. Dado que la respuesta puede ser muy grande, solo necesitas proporcionar el valor de la respuesta módulo $998244353$.

Entrada

La primera línea contiene dos enteros positivos $n, k$ ($4 \le n \le 5 \times 10^5, 2 \le k \le 100$), que representan el número de nodos mágicos y el límite superior del número de colores de los nodos mágicos.

La segunda línea contiene $n$ enteros positivos, donde el $i$-ésimo entero representa el color $c_i$ del nodo mágico numerado con $i$ ($1 \le c_i \le k$).

La tercera línea contiene $n$ enteros positivos, donde el $i$-ésimo entero representa el valor de poder mágico $a_i$ del nodo mágico numerado con $i$ ($0 \le a_i < 998244353$).

Salida

Una línea con un solo entero, que representa el valor de la intensidad mágica del círculo mágico módulo $998244353$.

Ejemplos

Entrada 1

4 2
1 2 1 2
1 2 3 4

Salida 1

24

Entrada 2

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

Salida 2

786705612