409535: GYM103625 I Redbeard's Trials
Description
Redbeard, the leader of the great Red Pearl pirate ship, is trying to test his crew. His crew consists of $$$n$$$ pirates and he has prepared a set of $$$m$$$ trials for his crew.
However these trials have not taken place yet. Redbeard would love for the results to satisfy a few properties. One, each pirate should pass at least one trial, otherwise they would be too sad. Two, no pirate should complete all of the trials successfully, otherwise they would be too confident. And three, every trial should be completed by at least one crew member. In how many ways can the results of the trials occur such that all three of these properties hold? Results are considered distinct if some crew member has a different outcome on some trial.
Can you determine how many ways trials can result modulo $$$10^9 + 7$$$?
InputThe first line of input contains two space-separated integers $$$n$$$ ($$$1 \leq n \leq 1000$$$) and $$$m$$$ ($$$1 \leq m \leq 10$$$).
OutputOutput a single integer which represents the number of possible results satisfying Redbeard's desired properties modulo $$$10^9 + 7$$$.
ExamplesInput2 2Output
2Input
4 2Output
14