408032: GYM102964 F Krosh and arrays

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Krosh and arraystime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExamplesInput
4 3
Output
4
Input
2 2
Output
2

加入题单

上一题 下一题 算法标签: