题目描述

马蒂想要收集全部 $n$ 种不同类型的宝可梦。

在接下来的 $m$ 天里，他每天都会恰好抓到一只宝可梦。每天抓到哪一种宝可梦，与其他天相互独立。

现在他想知道：在这 $m$ 天结束后，恰好使得自己至少拥有全部 $n$ 种不同类型各一只，一共有多少种不同的抓取方案。

如果两种方案在某一天抓到的宝可梦种类不同，则认为这两种方案不同。

请你求出方案数对模数 $1102024631$ 取模后的结果。

输入格式

输入仅一行，包含两个正整数 $m,n$。

输出格式

输出一行一个整数，表示答案对 $1102024631$ 取模后的结果。

数据范围

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

子任务

只有通过某个子任务的全部测试点，才能获得该子任务的分数。

样例输入

3 2

样例输出

6

样例说明

如果用 $1$ 和 $2$ 表示两种宝可梦，那么满足条件的抓取序列共有如下 $6$ 种：

$\{1,1,2\}, \{1,2,1\}, \{1,2,2\}, \{2,1,1\}, \{2,1,2\}, \{2,2,1\}$。