SP3893 SPACESET - Space settlement

很久以前，在一个遥远的星系中，帝国建造了一座壮观的太空殖民地。这个殖民地共有 $m$ 层，每层有 $n$ 个定居点。太空定居点之间通过特定的航线相连，供飞船在上面航行。 每层的布局都是环形的，包含 $n$ 个太空定居点，形成了飞船的航行路径。在同一层内，飞船只能沿着环形路径移动。无论该层有多少定居点，环路始终保持存在。 层与层之间是分级组织的，彼此之间有良好的连接。每一层的每个定居点都与其上层和下层的所有定居点相连。如果顶部和底部的层不同，它们也会以相同的方式连接。 我们的冒险家汉·索洛希望在这些太空定居点之间运送人员。他的飞船能够导航一条恰好有 $k$ 个停靠点的路径，不多不少。 **注意事项：** 1. 在一次航程中，每个定居点可以被多次访问。 2. 路径被认为是由一系列顶点组成的序列，且相邻顶点之间有相连的边。如果两条路径在任意一个顶点上不同，则它们被视为不同路径。 3. 只有当最顶层和最底层不是同一层时，它们才会连接。 以下是图示，黑色圆点表示定居点，连接线表示环形和直线路径。

第一行输入一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行中，每行包含三个整数 $m$、$n$ 和 $k$。

输出共 $T$ 行，每行对应一个测试用例下可以走的路线数量，并对结果取模 $12345678$。 **本翻译由 AI 自动生成**