EOJ-自适应编程学习平台

如果思念永远五彩斑斓的话， 在映入红瞳的世界里， 我们谱写独一无二的爱恋。

在实现愿望的国度，魔法使二阶堂真红许下了这样一个愿望——想和某人相恋。 「但是，这是不可能的吧。」 二阶堂真红明白，自己没有身为女孩子的魅力，也许和某人相恋的那一天永远都不会到来…… 在世界尽头的古书店，身为神明的你聆听到了真红的愿望，你决定为真红创造出一个能和某人自由相恋、一个五彩斑斓的世界。

每一个世界都是一个长度为$n$的染色排列$p$，其中每个元素都被染上了某种颜色，有$m$种可能出现的颜色。作为神明的你自然清楚，世界的总数为$n!\times m^n$

记$color(p_i)$表示$p_i$的颜色。如果一个世界是五彩斑斓的，当且仅当对于任意正整数$i(1 \le i \le n)$满足$color(p_i) \neq color(p_{p_i})$

现在，你需要统计有多少个不同的五彩斑斓的世界，并对一个神秘质数$20040403$取模。之后你会从中选择一个世界为真红实现愿望

两个五彩斑斓的世界$p$、$q$被认为是不同的，当且仅当以下条件至少有一条成立：

1.存在正整数$i$, 有$p_i \neq q_i$

2.存在正整数$i$、$j$, 有$p_i=q_j$并且$color(p_i) \neq color(q_j)$

「恋爱啊，恋爱，我办不到的这件事，就由你来实现」

第一行，一个正整数$T (1 \le T \le 100)$，表示数据组数

接下来$T$行，每行两个正整数，分别为排列长度$n (1 \le n \le 4000)$、颜色种数($1 \le m \le 1000000000$)

保证$\sum_{}^{}n \le 4000$

共$T$行，每行一个整数，表示不同的五彩斑斓的世界的个数