I. Palagapos
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After studying evolution for years, Charles Darwin stumbled upon a new archipelago: The Palagapos. He is especially fascinated by the species of turtles native to the island, and has been monitoring the DNA of the turtles on the islands.

For simplicity, a strand of DNA can be represented as an array of length $$$n$$$ containing integers ranging from $$$1$$$ to $$$k$$$. Let $$$a$$$ be a strand of DNA. A mutation of $$$a$$$ is an operation that consists of the following steps:

  • Select an index $$$i$$$ such that $$$1 \leq i \leq n$$$ and $$$a_i \lt k$$$.
  • Set $$$a_i \gets a_i + 1$$$.

Now, for DNA strands $$$a$$$ and $$$b$$$, define the function $$$f(a, b)$$$ to be the maximum number of mutations that could be applied to $$$a$$$ until $$$b$$$ is not lexicographically larger than $$$a$$$ for the first time.

Darwin wants to know the sum of $$$f(a[i,j], b[i,j])$$$ for all $$$1 \leq i \leq j \leq n$$$, where $$$a[i,j]$$$ represents the subarray of $$$a$$$ consisting of the elements $$$a_i, a_{i+1}, ..., a_{j}$$$. Please help Darwin!

Input

The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^9$$$) — denoting the length of the DNA sequences and the upper bound on the range of values in the sequences, respectively. The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, ... a_n$$$ ($$$1 \leq a_i \leq k$$$) — denoting the values in Darwin's first DNA sequence. The third line contains $$$n$$$ space-separated integers $$$b_1, b_2, ... b_n$$$ ($$$1 \leq b_i \leq k$$$) — denoting the values in Darwin's second DNA sequence.

Output

Output a single integer, denoting the sum that Darwin wants to know. Since this value can be quite large, output it modulo the prime $$$998244353$$$.

Examples
Input
2 3
2 1
2 2
Output
2
Input
3 4
1 2 2
3 4 1
Output
18