时间限制: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


题目来源

没有写明来源