说明

马蒂想要收集全部 $n$ 种不同的宝可梦。在为期 $m$ 天的时间段内，他每天恰好捕捉一只宝可梦。他对每一天的选择是独立于其他天的。现在他想知道，在 $m$ 天结束后，有多少种方式可以确保他已经捕获了至少每种不同的宝可梦各一只。

遗憾的是，作为某所大学的一年级新生，他正忙于处理其他问题（比如开设银行账户之类的琐事），因此把这个任务交给你来解决。

两种方案被认为是不同的，当且仅当在某一天中，两种方案所捕获的宝可梦种类不同。

输入格式

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

输出格式

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

3 2

6

提示

样例 1 解释

如果我们用 $1$ 和 $2$ 表示两种不同的宝可梦种类，那么按天数顺序的所有可能方案为：$\{1,1,2\}$、$\{1,2,1\}$、$\{1,2,2\}$、$\{2,1,1\}$、$\{2,1,2\}$、$\{2,2,1\}$。

子任务

只有当成功通过某子任务所对应的所有测试点时，才能获得该子任务的分数。

限制条件

• $1 \le m \le 10^{18}$
• $1 \le n \le 10^7$

翻译由 Qwen3.5-397B-A17B 完成