题目描述

在一棵大小为 $n+3$ 的树中，点集为 $\{A,B,C,1,2,\cdots,n\}$。

已知每条边的长度为正整数，且标号为 $i$ 的点到 $A,B,C$ 的距离分别是 $d_{Ai},d_{Bi},d_{Ci}$，求共有多少种不同的树满足要求。

两棵树不同，当且仅当边集不同，或者某条边的权值不同。

输入格式

多组测试数据。

第一行一个数 $T$，表示数据组数。

对于每组测试数据，第一行一个数 $n$。

接下来 $3$ 行，每行 $n$ 个数，分别表示 $d_{Ai},d_{Bi},d_{Ci}$。

输出格式

对于每组测试数据，输出答案模 $10^9+9$。

1
1
1
2
3

6

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 50$，$1\leq T\leq 40$，$1\leq d_{Ai},d_{Bi},d_{Ci}\leq 10^8$。