Description

A long narrow strip of paper is evenly divided into $n$ cells, numbered from $1$ to $n$. Each cell is colored with a color $color_i$ (represented by an integer from $[1, m]$), and a number $number_i$ is written on it.

Define a special triplet $(x, y, z)$, where $x$, $y$, $z$ are indices of cells on the strip, satisfying both of the following conditions:

1. $x$, $y$, $z$ are integers, $x < y < z$, $y - x = z - y$.
2. $color_x = color_z$.

The score of such a triplet is defined as $(x+z) \times (number_x+number_z)$. The score of the entire strip is the sum of the scores of all triplets that satisfy the conditions. This score can be very large; you only need to output the remainder when the total score is divided by $10007$.

Input Format

The first line contains two positive integers $n$ and $m$ separated by a space. $n$ is the number of cells on the strip, and $m$ is the number of colors.

The second line contains $n$ positive integers separated by spaces; the $i$-th number is the number $number_i$ written on cell $i$.

The third line contains $n$ positive integers separated by spaces; the $i$-th number is the color $color_i$ of cell $i$.

Output Format

A single integer, the remainder of the total score modulo $10007$.

6 2
5 5 3 2 2 2
2 2 1 1 2 1

82

15 4
5 10 8 2 2 2 9 9 7 7 5 6 4 2 4
2 2 3 3 4 3 3 2 4 4 4 4 1 1 1

1388

Hint

Sample 1 Explanation.

The strip is as shown in the figure in the problem description.

All valid triplets are: $(1, 3, 5)$, $(4, 5, 6)$.

Therefore, the total score is $(1 + 5) \times (5 + 2) + (4 + 6) \times (2 + 2) = 42 + 40 = 82$.

Constraints:

• For testdata groups $1$ to $2$, $1 \le n \le 100$, $1 \le m \le 5$.
• For testdata groups $3$ to $4$, $1 \le n \le 3000$, $1 \le m \le 100$.
• For testdata groups $5$ to $6$, $1 \le n \le 10^5$, $1 \le m \le 10^5$, and no color appears more than $20$ times.
• For all $10$ testdata groups, $1 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le color_i \le m$, $1 \le number_i \le 10^5$.

Translated by ChatGPT 5