Connecting switches to bulbs

Count the number of functions from A numbered switches onto B numbered bulbs, modulo 1000000007, i.e. B! times Stirling number of the second kind S(A, B).

Medium6CombinatoricsDynamic programmingMathNumber theoryNo attempts yetTime limit1sMemory limit64 MB

Description

Examples7

Problem

Mirko started a job as an electrician. On his first day the task is this: wire $A$ switches to $B$ bulbs so that every switch is connected to exactly one bulb, and every bulb has at least one switch connected to it.

How many ways can Mirko do it? The switches and the bulbs are all numbered. Two wirings count as different when at least one switch is not connected to the same bulb in both of them.

Input

The first line contains the number of switches $A$ and the number of bulbs $B$ , separated by a space. Both are natural numbers with $A, B \le 100000$ .

Output

Print the number of wirings on the first line. That number can be very large, so print only its remainder modulo $1000000007$ .