题目描述

一条狭长的纸带被均匀划分出了 ${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) ∗}$ ${(NUMBER_x + NUMBER_z)}$。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 ${10,007}$ 所得的余数即可。

输入格式

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

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

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

输出格式

共一行，一个整数，表示所求的纸带分数除以 ${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

数据范围与提示

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

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