Ay uczy się magii na Uniwersytecie Magii Ranoa!

Dzisiaj Ay zgłębia wiedzę o kręgach magicznych. Krąg magiczny przed nią składa się z okręgu i $n$ węzłów magicznych rozmieszczonych na jego obwodzie. Te $n$ węzłów dzieli okrąg na $n$ równych części i są one ponumerowane zgodnie z ruchem wskazówek zegara od $1, 2, \dots, n$. Węzeł magiczny o numerze $i$ ma kolor $c_i$ oraz wartość magiczną $a_i$, gdzie $c_i \le k$. Jeśli dwa węzły magiczne mają ten sam kolor, są one połączone magicznym odcinkiem tego samego koloru, którego wartość magiczna jest iloczynem wartości magicznych połączonych węzłów. Jeśli dwa magiczne odcinki o różnych kolorach przecinają się, generują siłę magiczną równą iloczynowi wartości magicznych tych dwóch odcinków. Całkowita siła magiczna kręgu magicznego to suma sił magicznych generowanych przez każdą parę przecinających się odcinków o różnych kolorach.

Teraz Ay chce poznać wartość siły magicznej kręgu magicznego przed nią. Ponieważ wynik może być bardzo duży, należy podać go modulo $998244353$.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n, k$ ($4 \le n \le 5 \times 10^5, 2 \le k \le 100$), oznaczające liczbę węzłów magicznych oraz górny limit liczby kolorów węzłów.

Druga linia zawiera $n$ liczb całkowitych, gdzie $i$-ta liczba oznacza kolor $c_i$ węzła o numerze $i$ ($1 \le c_i \le k$).

Trzecia linia zawiera $n$ liczb całkowitych, gdzie $i$-ta liczba oznacza wartość magiczną $a_i$ węzła o numerze $i$ ($0 \le a_i < 998244353$).

Wyjście

Jedna liczba całkowita oznaczająca wartość siły magicznej kręgu magicznego po wykonaniu operacji modulo $998244353$.

Przykład 1

Wejście 1

4 2
1 2 1 2
1 2 3 4

Wyjście 1

24

Przykład 2

Wejście 2

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

Wyjście 2

786705612