Ayaka étudie la magie à l'Université de Magie de Ranoa !

Aujourd'hui, Ayaka étudie les cercles magiques. Le cercle magique devant elle est composé d'un cercle et de $n$ nœuds magiques situés sur ce cercle. Ces $n$ nœuds divisent le cercle en $n$ parties égales et sont numérotés de $1, 2, \dots, n$ dans le sens des aiguilles d'une montre. Le nœud magique numéroté $i$ possède une couleur $c_i$ et une valeur magique $a_i$, où $c_i \le k$. Si deux nœuds magiques ont la même couleur, ils sont reliés par un segment magique de cette même couleur, dont la valeur magique est égale au produit des valeurs magiques des deux nœuds qu'il relie. Si deux segments magiques de couleurs différentes se croisent, ils génèrent une intensité magique égale au produit des valeurs magiques de ces deux segments. L'intensité magique totale du cercle magique est la somme des intensités magiques générées par chaque paire de segments de couleurs différentes qui se croisent.

Maintenant, Ayaka veut connaître la valeur de l'intensité magique du cercle magique devant elle. Comme la réponse peut être très grande, vous devez donner la réponse modulo $998244353$.

Entrée

La première ligne contient deux entiers positifs $n, k$ ($4 \le n \le 5 \times 10^5, 2 \le k \le 100$), représentant le nombre de nœuds magiques et la limite supérieure du nombre de couleurs des nœuds magiques.

La deuxième ligne contient $n$ entiers positifs, où le $i$-ième entier représente la couleur $c_i$ du nœud magique numéroté $i$ ($1 \le c_i \le k$).

La troisième ligne contient $n$ entiers positifs, où le $i$-ième entier représente la valeur magique $a_i$ du nœud magique numéroté $i$ ($0 \le a_i < 998244353$).

Sortie

Une ligne contenant un entier, représentant la valeur de l'intensité magique du cercle magique modulo $998244353$.

Exemples

Entrée 1

4 2
1 2 1 2
1 2 3 4

Sortie 1

24

Entrée 2

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

Sortie 2

786705612