You are given three integers n, x, and y.

An event is being held for n performers. When a performer arrives, they are assigned to one of the x stages. All performers assigned to the same stage will perform together as a band, though some stages might remain empty.

After all performances are completed, the jury will award each band a score in the range [1, y].

Return the total number of possible ways the event can take place.

Since the answer may be very large, return it modulo 109 + 7.

Note that two events are considered to have been held differently if either of the following conditions is satisfied:

• Any performer is assigned a different stage.
• Any band is awarded a different score.

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= n, x, y <= 1000