Problem Description

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.

Input Format

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

Output Format

Print the answer modulo $1102024631$ to standard output.

3 2

6

Hint

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

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