题目描述

小$W$最近迷上了日本动漫，每天都有无数部动漫的更新等着他去看，所以他必须将所有的动漫排个顺序，当然，虽然有无数部动漫，但除了$1$号动漫，每部动漫都有且仅有一部动漫是它的前传（父亲），也就是说，所有的动漫形成一个树形结构。而动漫的顺序必须满足以下两个限制： ①一部动漫的所有后继（子孙）都必须排在它的后面。 ②对于同一部动漫的续集（孩子），小W喜爱度高的须排在前面。 光排序小$W$还不爽，他想知道一共有多少种排序方案，并且输出它$\bmod 10007$的答案。

输入

第一行表示$T$表示数据组数。接下来每组数据第一行$n$表示有多少部动漫等待排序，接下来$n$行每行第一个数$tot$表示这部动漫有多少部续集，接下来$tot$个数按照小$W$喜爱从大到小给出它的续集的编号。

输出

每组数据一行数$ans$，表示答案$\bmod 10007$的结果。

输入样例

1
5
3 4 3 2
0
1 5
0
0

输出样例

2

提示

【数据规模】 对于30%的数据，$n≤10$。 对于60%的数据，$n≤100$。 对于100%的数据，$n≤1000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。