Marti wants to collect all $n$ different types of Pokémon. Every day over a period of $m$ days, he will catch exactly one Pokémon. His choice for a given day is independent of the other days. Now he is wondering in how many ways, after $m$ days, he will have caught at least one of each of the $n$ different types.
Unfortunately, as a freshman at a certain university, he is busy with other problems (like opening a bank account, what else 😉), so he leaves the task to you.
Two ways are considered different if, on any day of the period, the Pokémon caught in the two ways are of a different type.
Input
The only line of standard input contains the natural numbers $m$ and $n$.
Output
On the only line of standard output, print the found number modulo $1102024631$.
Constraints
- $1 \le m \le 10^{18}$
- $1 \le n \le 10^7$
Subtasks
| Subtask | Points | Additional Constraints |
|---|---|---|
| 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 | None |
Points for a given subtask are awarded only if all test cases provided for it are passed successfully.
Examples
Input 1
3 2
Output 1
6
Note 1
If we denote the types as 1 and 2, the ways corresponding to the days are $\{1, 1, 2\}, \{1, 2, 1\}, \{1, 2, 2\}, \{2, 1, 1\}, \{2, 1, 2\}, \{2, 2, 1\}$.