SP8096 SPQUEUE - Queue

:::warning[警告]{open} 这道题在 SPOJ 上被隐藏，不保证能正常提交。 :::

在一些特别的场合，Nadia 的公司会为所有员工提供特殊的午餐。食品供应开始之前，所有员工都需要在餐台前排成一列。公司制定了一条排队规则：如果 Abul 是 Babul 的主管，并且 Abul 站在队列的第 $k$ 个位置，那么 Babul 不能站在第 $1$ 到第 $k-1$ 个位置。公司共有 $N$ 名员工，每个人都有一位主管，只有一个例外，没有主管。 你的任务是计算可以有多少种不同的方式来安排这个队列。请放心，至少存在一种排队方式符合要求。

第一行是测试用例的数量。 对于每个测试用例： - 第一行包含两个整数 $M$ 和 $N$，其中 $M$ 用于取模运算。 - 接下来的 $N-1$ 行，每行包含一个整数，表示第 $i$ 个员工的主管。

对于每个测试用例，输出这个问题的排队方式总数对 $M$ 取模后的结果。

- 当测试用例较多时，$1 \leq N \leq 10^5$； - 当测试用例只有一个时，$1 \leq N \leq 5\times 10^5$； - $1 \leq M \leq 10^9$。