Marti 想要收集所有 $n$ 种不同类型的宝可梦。在 $m$ 天的时间段内，他每天都会恰好捕捉一只宝可梦。他在某一天捕捉宝可梦的选择与其他日期无关。现在他想知道，在 $m$ 天之后，他已经捕捉到至少一只所有 $n$ 种不同类型宝可梦的方法总数。
遗憾的是，作为某大学的一名大一新生，他正忙于处理其他问题（比如开立银行账户之类的琐事），因此他把这个问题留给了你。
如果两种方案在某一天捕捉到的宝可梦类型不同，则认为这两种方案是不同的。
输入格式
从标准输入读取一行，包含两个自然数 $m$ 和 $n$。
输出格式
在标准输出的一行中打印所求的方法数，结果对 $1102024631$ 取模。
数据范围
- $1 \le m \le 10^{18}$
- $1 \le n \le 10^7$
子任务
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 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
3 2
输出 1
6
说明 1
如果我们用 1 和 2 表示宝可梦的类型，那么按天数排列的方案分别为 $\{1, 1, 2\}, \{1, 2, 1\}, \{1, 2, 2\}, \{2, 1, 1\}, \{2, 1, 2\}, \{2, 2, 1\}$。