刚被解救出来的某 和小 需要立即找到通往正常世界的道路。然而，此时的小 已经耗尽了魔力，无法使出 之力来救出他们自己了。然而，不曾施过法的某 却还有很多的魔力，某 不会施法，所以他需要用某种方式来将自己的魔力转移到小 身上。不过这种魔力转移是相当危险的，必须严格控制好转移的量，否则后果不堪设想。应当转移的魔力值可以由某种方式计算出来，但是现在某 已经没有精力去算这种东西了，你能帮帮他吗？

计算的方法为：有一个 的矩阵，需要在里面的每个格子里填入非负整数 满足 。记第 行的最大值为 ，记第 列的最大值为 ，问对于所有填数的方案，可以构成多少组不同的 。 与 不同当且仅当至少有一组 满足 或至少有一组 满足 。这个方案总数便是需要转移的魔力值。

第一行一个数 ，表示问题组数。后 行每行三个数 描述了每个问题。

每行一个数表示每个问题的答案。请将答案对 取模。

对于 的数据，满足 。