綾はラノア魔法大学で魔法を学んでいます！ 今日、綾は魔法陣に関する知識を学んでいます。綾の目の前にある魔法陣は、1つの円と円周上の $n$ 個の魔法ノードで構成されています。これら $n$ 個の魔法ノードは円を $n$ 等分しており、時計回りに $1, 2, \dots, n$ と番号が振られています。番号 $i$ の魔法ノードには色 $c_i$ と魔力値 $a_i$ があり、$c_i$ の値は $k$ 以下です。もし2つの魔法ノードの色が同じであれば、その2つのノードは同じ色の魔法線分で結ばれ、この魔法線分の魔力値は、結ばれた2つの魔法ノードの魔力値の積となります。もし色の異なる2つの魔法線分が交差する場合、それら2つの魔法線分の魔力値の積に等しい魔法強度が生成されます。魔法陣全体の魔法強度は、交差する異色の線分のすべてのペアから生成される魔法強度の総和です。

今、綾は目の前にある魔法陣の魔法強度を知りたいと考えています。答えは非常に大きくなる可能性があるため、$998244353$ で割った余りを求めてください。

入力

1行目に2つの正整数 $n, k$ ($4 \le n \le 5 \times 10^5, 2 \le k \le 100$) が与えられ、それぞれ魔法ノードの数と魔法ノードの色の数の上限を表します。

2行目に $n$ 個の正整数が与えられ、$i$ 番目の整数は番号 $i$ の魔法ノードの色 $c_i$ ($1 \le c_i \le k$) を表します。

3行目に $n$ 個の正整数が与えられ、$i$ 番目の整数は番号 $i$ の魔法ノードの魔力値 $a_i$ ($0 \le a_i < 998244353$) を表します。

出力

1行に1つの整数を出力してください。これは魔法陣の魔法強度を $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