树
时间限制：3s 空间限制：512MB
题目描述
在一棵大小为n+3 的树中，点集为{A,B,C,1,2,......n}。
已知每条边的长度为正整数，且标号为i的点到 A,B,C的距离分别是 dAi,dBi,dCi，求共有多少种不同的树满足要求。
两棵树不同，当且仅当边集不同，或者某条边的权值不同。
输入格式
多组测试数据。
第一行一个数T，表示数据组数。
对于每组测试数据，第一行一个数n 。
接下来3行，每行n个数。三行分别表示dA,dB,dC 。
输出格式
对于每组测试数据，输出答案模 10^9 +9 。
样例输入
1 1 1 2 3
样例输出
6
提示
1<=N<=50 T<=40,1<=DAi,DBi,DCi<=10^8
题目来源
没有写明来源