题目描述

在法鲁姆的丝绸平原上，有 $n$ 只昆虫。每只昆虫都有三种角色之一：恰好一只歌者、$s-1$ 只回声者，以及 $n-s$ 只沉默者。

时刻 $0$，唯一的歌者发出一声呼喊。声波不会衰减，并以相同的速度均匀地向各个方向传播：到达距离歌者为 $d$ 的位置，需要 $d$ 单位时间。此后，每只回声者都在第一次听到其他昆虫的呼喊的时刻，立即发出一声呼喊。这些声波的传播方式与最初的声波相同。不同声波之间不会相互作用，也不会影响彼此。

一名听众位于 $(0,0)$，记录声波到达的时刻：首先恰好听到一声呼喊；经过一段非零的时间后，同时听到另外 $c_2$ 声呼喊；再经过一段非零的时间后，听到另外 $c_3$ 声呼喊；如此一共出现 $k$ 个到达时刻，得到序列 $c_1,c_2,c_3,\ldots,c_k$。

注意，每只非沉默者都只呼喊一次，所以 $\sum_{i=1}^{k}c_i=s$。

已知平面上所有 $n$ 只昆虫的坐标。请计算有多少种方法，可以从中选出恰好一只歌者和恰好 $s-1$ 只回声者，使听众的观察结果与给定序列 $c_i$ 一致。其余昆虫自动成为沉默者。答案对 $10^9+7$ 取模。

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$，表示测试数据组数，$1\le t\le500$。接下来给出各组测试数据。

每组数据第一行包含整数 $n,k$，分别表示昆虫数量，以及预期在 $(0,0)$ 听到呼喊的不同到达时刻数量，$1\le n\le1000$，$1\le k\le\min(n,10)$。

第二行包含 $n$ 个整数，表示昆虫的横坐标 $x_i$。第三行也包含 $n$ 个整数，表示昆虫的纵坐标 $y_i$，$|x_i|,|y_i|\le10^9$。

第四行包含整数 $c_1,\ldots,c_k$，表示在不同到达时刻，听众分别听到多少声呼喊，$1\le c_i\le n$，$c_1=1$，$\sum_{i=1}^{k}c_i\le n$。这些数按照时间先后顺序给出。

保证所有测试数据的 $n$ 之和不超过 $1000$。

输出格式

对于每组测试数据，输出一个整数，表示符合要求的角色分配方法数量，对 $10^9+7$ 取模。

8
1 1
1
1
1
2 1
2 0
0 1
1
2 2
1 2
0 0
1 1
3 2
1 0 2
0 1 0
1 2
3 2
0 1 0
0 0 1
1 2
4 3
0 1 0 1
0 0 1 1
1 2 1
6 3
0 1 0 1 -1 1
0 0 1 1 1 -1
1 2 3
3 2
1 0 -1
0 1 0
1 1

1
2
1
0
1
1
1
6

提示

注意，$c_1=1$ 并不保证任意一只昆虫都能成为歌者。以下解释中，声音的传播速度为 $1$。

1. 第一组数据中，只有一只位于 $(1,1)$ 的昆虫。让它成为歌者后，听众在时刻 $\sqrt2$ 听到一声呼喊。
2. 第二组数据中，两只昆虫分别位于 $(2,0)$ 和 $(0,1)$。任意一只都可以成为歌者：选择第一只时，听众在时刻 $2$ 听到呼喊；选择第二只时，听众在时刻 $1$ 听到呼喊。两种情况均满足要求。
3. 第三组数据中，两只昆虫的坐标分别为 $(1,0)$ 和 $(2,0)$。如果让第一只成为回声者，两声呼喊会同时到达听众的位置，不满足题目要求。