Ling is studying magic at the Ranoa University of Magic!

Today, Ling is learning about magic circles. The magic circle in front of her consists of a circle and $n$ magic nodes on it. These $n$ magic nodes divide the circle into $n$ equal parts and are numbered $1, 2, \dots, n$ in clockwise order. The magic node numbered $i$ has a color $c_i$ and a magic value $a_i$, where $c_i \le k$. If two magic nodes have the same color, they are connected by a magic line segment of that color, and the magic value of this line segment is the product of the magic values of the two nodes it connects. If two magic line segments of different colors intersect, they produce a magic intensity equal to the product of the magic values of the two line segments. The total magic intensity of the magic circle is the sum of the magic intensities produced by every pair of intersecting line segments of different colors.

Now, Ling wants to know the value of the magic intensity of the magic circle in front of her. Since the answer may be very large, you only need to output the answer modulo $998244353$.

Input

The first line contains two positive integers $n, k$ ($4 \le n \le 5 \times 10^5, 2 \le k \le 100$), representing the number of magic nodes and the upper limit of the number of colors for the magic nodes.

The second line contains $n$ positive integers, where the $i$-th integer represents the color $c_i$ of the magic node numbered $i$ ($1 \le c_i \le k$).

The third line contains $n$ positive integers, where the $i$-th integer represents the magic value $a_i$ of the magic node numbered $i$ ($0 \le a_i < 998244353$).

Output

Output a single integer representing the magic intensity of the magic circle modulo $998244353$.

Examples

Input 1

4 2
1 2 1 2
1 2 3 4

Output 1

24

Input 2

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

Output 2

786705612