綾正在拉諾亞魔法大學學習魔法！

今天，綾學習的是魔法陣的相關知識。綾面前的魔法陣由一個圓和圓上的 $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