P15844 [Bulgarian NOI 2024] 宝可梦 / pokemons

马蒂想要收集全部 $n$ 种不同的宝可梦。在为期 $m$ 天的时间段内，他每天恰好捕捉一只宝可梦。他对每一天的选择是独立于其他天的。现在他想知道，在 $m$ 天结束后，有多少种方式可以确保他已经捕获了至少每种不同的宝可梦各一只。 遗憾的是，作为某所大学的一年级新生，他正忙于处理其他问题（比如开设银行账户之类的琐事），因此把这个任务交给你来解决。 两种方案被认为是不同的，当且仅当在某一天中，两种方案所捕获的宝可梦种类不同。

从标准输入的单一行读入两个自然数 $m$ 和 $n$。

在标准输出，输出答案对模数 $1102024631$ 取模后的结果。

### 样例 1 解释 如果我们用 $1$ 和 $2$ 表示两种不同的宝可梦种类，那么按天数顺序的所有可能方案为：$\{1,1,2\}$、$\{1,2,1\}$、$\{1,2,2\}$、$\{2,1,1\}$、$\{2,1,2\}$、$\{2,2,1\}$。 ### 子任务 | 子任务 | 分数 | 额外限制条件 | |:------:|:----:|:------------------------:| | $1$ | $5$ | $m, n \le 8$ | | $2$ | $5$ | $m, n \le 19$ | | $3$ | $10$ | $m, n \le 7000$ | | $4$ | $5$ | $n \le 100000, m \le n + \sqrt{n}$ | | $5$ | $50$ | $n \le 1500000$ | | $6$ | $25$ | 无 | 只有当成功通过某子任务所对应的所有测试点时，才能获得该子任务的分数。 ### 限制条件 - $1 \le m \le 10^{18}$ - $1 \le n \le 10^7$ 翻译由 Qwen3.5-397B-A17B 完成