题目描述

你潜心研究半生，成为了世界上最出色的魔法师，尤其擅长施展魔法阵。

你有 $n$ 块魔法石，第 $i$ 块魔法石的魔力为 $i$。你可以施展出 $n!$ 种魔法阵，每种魔法阵都可以表示为一个排列。

但是魔法阵肯定是不能一直维持的。具体的，施展出一个魔法阵后，在每一天里，每一块魔力小于其相邻魔法石的魔法石都会失去魔法，而一天结束后你还需要移除所有在这一天中失去魔法的魔法石。当魔法阵只剩下最后一块魔法石时，阵法失效。

形式化地说，假设魔法阵为一个长度为 $n$ 的排列 $p_{1\sim n}$：

• 在第一天前，令 $a=p$。

• 接下来每一天，令 $len$ 为 $a$ 的当前长度。对于所有满足

  • $a_i < a_{i-1}\ (1<i\le len)$ 或
  • $a_i < a_{i+1}\ (1\le i < len)$

  的 $i$，将 $a_i$ 删去（在这一天结束时将所有需要删除的数同时删去）。

• 若某天删去后 $len=1$，那么魔法阵在该天后失效。

你想知道，在所有你能施展出的魔法阵中，有多少种魔法阵在恰好 $m$ 天后失效？

答案可能会很大，你只需要输出其对 $mod$ 取模的结果。

输入格式

本题采用多组测试。第一行两个非负整数 tid, T，分别表示测试点编号和数据组数。特别的，在样例中 tid=0。

对于每组数据：一行三个正整数 $n,m,mod$。

输出格式

共 $T$ 行，每行一个整数，表示一组数据的答案。

样例

样例输入

0 3
5 2 209029109
5 3 209029109
5 4 209029109

样例输出

100
4
0

样例解释

对于 $n=5,m=3$，所有满足条件的排列为：

• $\{4,1,3,2,5\}$、$\{4,2,3,1,5\}$、$\{5,1,3,2,4\}$、$\{5,2,3,1,4\}$。

其中魔法阵 $\{4,1,3,2,5\}$ 每一天的状态变化为：

• $\{4,1,3,2,5\}\rightarrow \{4,3,5\}\rightarrow \{4,5\}\rightarrow \{5\}$。

数据范围与提示

• 对于 20% 的数据：$n\le 10$。
• 对于 40% 的数据：$n\le 60$。
• 对于 60% 的数据：$n\le 200$。
• 对于另外 5% 的数据：$m=1$。
• 对于另外 15% 的数据：$m=2$。
• 对于 100% 的数据：$1\le T\le 3$，$2\le n\le 1000$，$1\le m\le n$，$1\le mod\le 10^9+7$。