408032: GYM102964 F Krosh and arrays

Krosh has two numbers $$$n$$$ and $$$m$$$. He calls an array consisting of $$$k$$$ elements good, if any two adjacent numbers differ only by one, so for any $$$1 \le i \le k - 1$$$ $$$|a_i - a_{i + 1}| = 1$$$. Array of length $$$1$$$ is always good. Help Krosh to calculate number of arrays of size $$$m$$$ elements consisting of natural numbers from $$$1$$$ to $$$n$$$ such that every number from $$$1$$$ to $$$n$$$ appears at least once in this array. Answer can be large so output it modulo $$$10^9+7$$$. Two arrays are different if there exists a position in which two elements differ.

You are given two natural numbers $$$1 \le m \le 2000$$$, $$$1 \le n \le m$$$.

Output answer modulo $$$10^9+7$$$.

4 3

4

2 2

2