Problem Background

NOIP2015 Junior Group T3

Problem Description

A narrow strip of paper is evenly divided into \( n \) squares, numbered from 1 to \( n \). Each square is dyed with a color \( color_i \) (represented by an integer in the range \([1, m]\)) and has a number \( number_i \) written on it.

A special triplet is defined as \((x, y, z)\), where \(x, y, z\) represent the numbers of the squares on the paper. This triplet must satisfy 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 paper is the sum of the scores of all valid triplets. Since this score can be very large, you only need to output the remainder of the total score divided by \(10007\).

Input Format

The first line contains two positive integers \( n \) and \( m \), separated by a space. \( n \) represents the number of squares on the paper, and \( m \) represents the number of different colors.

The second line contains \( n \) positive integers separated by spaces, where the \( i \)-th number represents the number \( number_i \) written on the square numbered \( i \).

The third line contains \( n \) positive integers separated by spaces, where the \( i \)-th number represents the color \( color_i \) of the square numbered \( i \).

Output Format

A single integer representing the remainder of the paper's score divided by \(10007\).

Sample Input and Output

Input Sample #1

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

Output Sample #1

82

Input Sample #2

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

Output Sample #2

1388

Notes

Sample 1 Explanation

The paper strip is as shown in the problem description.

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

Thus, the score of the paper is \((1 + 5) \times (5 + 2) + (4 + 6) \times (2 + 2) = 42 + 40 = 82\).

For the first to second sets of data, \(1 \leq n \leq 100, 1 \leq m \leq 5\);

For the third to fourth sets of data, \(1 \leq n \leq 3000, 1 \leq m \leq 100\);

For the fifth to sixth sets of data, \(1 \leq n \leq 100000, 1 \leq m \leq 100000\), and no color appears more than 20 times;

For all 10 sets of data, \(1 \leq n \leq 100000, 1 \leq m \leq 100000, 1 \leq color_i \leq m, 1 \leq number_i \leq 100000\).

见题面 Input 部分

见题面 Output 部分