Hanhan has two boxes of matches, each containing $n$ matches, and each match has a specific height. Now, arrange the matches in each box into a row. The heights of the matches in each row are distinct. The distance between the two rows of matches is defined as: $\sum_{i=1}^{n}(a_i - b_i)^2$, where $a_i$ represents the height of the $i$-th match in the first row, and $b_i$ represents the height of the $i$-th match in the second row.

You can swap the positions of any two adjacent matches in each row. Please find the minimum number of swaps required to minimize the distance between the two rows of matches. If this number is too large, output the result of the minimum number of swaps modulo $99,999,997$.

Input

The input consists of three lines: The first line contains a single integer $n$, representing the number of matches in each box. The second line contains $n$ integers, separated by spaces, representing the heights of the matches in the first row. The third line contains $n$ integers, separated by spaces, representing the heights of the matches in the second row.

Output

Output a single line containing the minimum number of swaps modulo $99,999,997$.

Examples

Input 1

4
2 3 1 4
3 2 1 4

Output 1

1

Note 1

The minimum distance is $0$, and the minimum number of swaps required is $1$. For example, swap the first two matches in the first row or the first two matches in the second row.

Input 2

4
1 3 4 2
1 7 2 4

Output 2

2

Note 2

The minimum distance is $10$, and the minimum number of swaps required is $2$. For example, swap the middle two matches in the first row, then swap the last two matches in the second row.

Constraints

For $10\%$ of the data, $1 \le n \le 10$; For $30\%$ of the data, $1 \le n \le 100$; For $60\%$ of the data, $1 \le n \le 1,000$; For $100\%$ of the data, $1 \le n \le 100,000$, $0 \le \text{match height} \le 2^{31} - 1$.