U132324 火车站

有一个奇奇怪怪的火车站，奇奇怪怪的站长JTZ想要解决一个奇奇怪怪的问题。 

现在有 $N$ 列火车要进出站，对于同一列车进站和出站有且只有一次鸣笛，笛声有 $1-M$ 种音调，要求相邻的两次鸣笛之间音调的差的绝对值不能小于 $K$ （不鸣笛笛声音调看作$1e100$ ）。不然耳朵不好的车站管理员XYH分不清楚是哪一列车，现在XYH给出了每一列火车的进出，JTZ想知道总共有多少种鸣笛的方案，而他又不想太麻烦，所以只需要方案数除以 $43621789$ 的余数。 某中学八年级大佬RSJ知道了这个消息后，觉得太简单了，几下算出了结果 $x$ （取余数后）。于是他想让你算出 $ M^x \mod 43621789$ 。

无

无

**图非常重要** ### 样例解释： 样例1： $x=4,M=1$ 答案为 $ 1^4 \mod 43621789=1$ 样例2： $x=250,M=5$ 答案为 $ 5^{250} \mod 43621789=40308287$ ### 数据范围 **本题采用 Subtask** $\text{Subtask}\ 1$: 测试点 $1-5$ $30\%$ $N\le 3,M\le 7$ $\text{Subtask}\ 2$: 测试点 $6-12$ $40\%$ $N\le 100，M\le 7$ $\text{Subtask}\ 3$: 测试点 $13-20$ $40\%$ $N\le 500,M\le 7$ 你只有通过每个 $\text{Subtask}$ 的所有测试点才能获得该 $\text{Subtask}$ 的分值。 [题解](https://www.cnblogs.com/jiangtaizhe001/p/14405606.htmlhttps://www.cnblogs.com/jiangtaizhe001/p/14405606.html)