小 Z 最近在研究数学，尤其是分组问题最令小 Z 感兴趣。
分组问题是指将 个不同的人分到若干组中，使得每个组中的人数一样，求方案数。譬如 时，不同的分组方案如下：
小 Z 自然不满足于此，他还想用 种颜色给这些方案染色，再计算染色的方案数。如 时，一共有 种分组方案，那么答案则是 种。
Your Task
给定 ，计算染色的方案数。
由于答案可能很大，请输出它对 取模后的结果。
第一行 表示数据组数
对于每组数据，仅一行
对于每组数据，在一行中输出答案
2 4 2 2 3
32 9
对于 的数据，，。
