Onto Functions

Difficulty: 2000 5000 ms 128 MB

combinatorics

Count the surjective (onto) functions from an N-element set to a K-element set, modulo 10⁹+7.

Input: one line with two integers N and K.

Output: the number of surjections mod 10⁹+7.

Constraints:

• 1 ≤ K ≤ N ≤ 10⁶

Sample Tests

3 2

6

2 2

2

Read the Editorial