题目描述

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

定义一种特殊的三元组：$\red{(x, y, z)}$，其中$\red{x，y，z}$都代表纸带上格子的编号，这里的三元组要求满足以下两个条件： 1.$\red{x, y, z}$都是整数, $\red{x < y < z, y−x = z−y}$ 2.$\red{COLOR_x}$ = $\red{COLOR_z}$

满足上述条件的三元组的分数规定为$\red{(x + z) ∗}$ $\red{(NUMBER_x + NUMBER_z)}$。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 $\red{10,007}$ 所得的余数即可。

输入格式

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

第二行有 $\red{n}$ 个用空格隔开的正整数，第$\red{ i }$个数字$\red{NUMBER_i}$ 代表纸带上编号为 $\red{i}$ 的格子上面写的数字。

第三行有 $\red{n }$个用空格隔开的正整数，第 $\red{i }$个数字$\red{COLOR_i}$ 代表纸带上编号为 $\red{i}$ 的格子染的颜色。

输出格式

共一行，一个整数，表示所求的纸带分数除以 $\red{10,007}$ 所得的余数。

样例

样例输入

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

数据范围与提示

对于第 $\red{1}$ 组至第$\red{ 2}$ 组数据，$\red{1 ≤ n ≤ 100}$, $\red{1 ≤ m ≤ 5}$； 对于第 $\red{3 }$组至第$\red{ 4}$ 组数据，$\red{{1 ≤ n ≤ 3000}, {1 ≤ m ≤ 100}};$

对于第 $\red{5}$ 组至第$\red{6}$ 组数据，$\red{1 ≤ n ≤ 100000}$,$\red{1 ≤ m ≤ 100000}$，且不存在出现次数超过 $\red{20}$ 的颜色； 对于全部 $\red{10}$ 组数据，$\red{{1 ≤n ≤ 100000},{1 ≤ m ≤ 100000}, {1 ≤ color_i ≤ m}, {1 ≤ number_i ≤ 100000。}}$