该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一条狭长的纸带被均匀划分出了 $n$ 个格子，格子编号从 $1$ 到 $n$。每个格子上都染了一种颜色 $color_i$（用 $[1,m]$ 当中的一个整数表示），并且写了一个数字 $number_i$。

定义一种特殊的三元组：$(x,y,z)$，其中 $x,y,z$ 都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：

1. $x,y,z$ 都是整数，$x<y<z$，且 $y-x=z-y$。
2. $color_x=color_z$。

满足上述条件的三元组的分数规定为 $(x+z) \times (number_x+number_z)$。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 $10007$ 所得的余数即可。

（术语说明：三元组是指由三个元素组成的有序组合。）

输入格式

第一行是用一个空格隔开的两个正整数 $n$ 和 $m$，$n$ 表示纸带上格子的个数，$m$ 表示纸带上颜色的种类数。

第二行有 $n$ 个用空格隔开的正整数，第 $i$ 个数字表示纸带上编号为 $i$ 的格子上面写的数字 $number_i$。

第三行有 $n$ 个用空格隔开的正整数，第 $i$ 个数字表示纸带上编号为 $i$ 的格子染的颜色 $color_i$。

输出格式

一个整数，表示所求的纸带分数除以 $10007$ 所得的余数。

样例输入

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

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

82

1388

样例解释

对于第一个样例，纸带上的格子编号为 $1$ 到 $6$，颜色和数字分别为：

• 格子 $1$：颜色 $2$，数字 $5$
• 格子 $2$：颜色 $2$，数字 $5$
• 格子 $3$：颜色 $1$，数字 $3$
• 格子 $4$：颜色 $1$，数字 $2$
• 格子 $5$：颜色 $2$，数字 $2$
• 格子 $6$：颜色 $1$，数字 $2$

所有满足条件的三元组为：$(1,3,5)$ 和 $(4,5,6)$。

对于 $(1,3,5)$：$x=1$，$y=3$，$z=5$，满足 $y-x=3-1=2$，$z-y=5-3=2$，且 $color_1=2$，$color_5=2$，颜色相等。分数为 $(1+5) \times (5+2) = 6 \times 7 = 42$。

对于 $(4,5,6)$：$x=4$，$y=5$，$z=6$，满足 $y-x=5-4=1$，$z-y=6-5=1$，且 $color_4=1$，$color_6=1$，颜色相等。分数为 $(4+6) \times (2+2) = 10 \times 4 = 40$。

总分数为 $42 + 40 = 82$。

数据范围

对于第 $1$ 组至第 $2$ 组数据，$1 \le n \le 100$，$1 \le m \le 5$；

对于第 $3$ 组至第 $4$ 组数据，$1 \le n \le 3000$，$1 \le m \le 100$；

对于第 $5$ 组至第 $6$ 组数据，$1 \le n \le 10^5$，$1 \le m \le 10^5$，且不存在出现次数超过 $20$ 的颜色；

对于全部 $10$ 组数据，$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$。