题目描述

在某个特殊的日子里，一家公司会为所有员工提供午餐。在取餐之前，所有员工必须在窗口前排成一列。

公司有 $N$ 名员工，编号为 $1\sim N$。员工 $1$ 没有主管；对于每个员工 $i\ (2\le i\le N)$，都给出了他的直属主管。

排队必须满足以下规则：任何员工都不能排在自己的主管之前。换句话说，如果员工 $u$ 是员工 $v$ 的主管，那么 $u$ 在队列中的位置必须严格早于 $v$。

题目保证至少存在一种合法排队方案。

请计算合法队列的总数，并对给定的整数 $M$ 取模。

输入格式

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

对于每组测试数据：

• 第一行两个整数 $M,N$；
• 接下来 $N-1$ 行，第 $i-1$ 行（$2\le i\le N$）包含一个整数 $p_i$，表示员工 $i$ 的主管编号。

输出格式

对于每组测试数据输出一行，一个整数，表示合法队列总数对 $M$ 取模的结果。

样例

1
2 2
1

1

数据范围

• 小数据：测试组数不超过 $10$，$N\le10^5$；
• 大数据：测试组数为 $1$，$N\le5\times10^5$；
• $1\le M\le10^9$；
• 题目保证主管关系至少存在一种合法拓扑序，因此不会形成有向环。