P15844 [Bulgarian NOI 2024] Pokémon / pokemons

Marty wants to collect all $n$ different types of Pokémon. Over a period of $m$ days, he catches exactly one Pokémon each day. His choice on each day is independent of the other days. Now he wants to know: after $m$ days, how many sequences of choices can guarantee that he has caught at least one of each different type of Pokémon. Unfortunately, as a first-year university student, he is busy dealing with other issues (such as trivial things like opening a bank account), so he leaves this task to you. Two plans are considered different if and only if, on some day, the Pokémon type caught in the two plans is different.

Read two natural numbers $m$ and $n$ from a single line of standard input.

Print the answer modulo $1102024631$ to standard output.

### Sample 1 Explanation If we use $1$ and $2$ to represent two different Pokémon types, then all possible sequences in chronological order are: $\{1,1,2\}$, $\{1,2,1\}$, $\{1,2,2\}$, $\{2,1,1\}$, $\{2,1,2\}$, $\{2,2,1\}$. ### Subtasks | Subtask | Score | 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 | You can get the score of a subtask only if you pass all test points of that subtask. ### Constraints - $1 \le m \le 10^{18}$ - $1 \le n \le 10^7$ Translated by ChatGPT 5