Transylvania is invaded by zombies, and the only way to save it from the upcoming calamity is to organise an epic army which can withstand the fight.
We are given N soldiers and M tanks. If there is any tank with no soldiers inside, then the war is lost. Hence, the soldiers have to be distributed in the M tanks. Additionally, we have M mathematicians who are going to compute the exact trajectories that tanks have to fire at in order to maximize the accuracy during the fight. However, mathematician i does not want to work in the ith tank for some unknown reason.
Print the number of possible arrangements mod 666013 such that every tank has one mathematician and at least one soldier inside.
Two configurations are different if there is at least one tank which does not contain exactly the same people inside.
Input
The first line of input contains two integers N and M.
Output
The only line of output should contain the requested number.
Restrictions
- 1 ≤ N, M ≤ 105
Sample
| Input | Output |
|---|---|
| 5 3 | 300 |
| 3 3 | 12 |
The problem requires you to count the number of surjections defined on a domain of cardinal N and codomain of cardinal M and multiply it by the number of derangements of M.
In order to count this we use Inclusion-Exclusion Principle in the following way:
Sum(K <- 0, M) (M choose K) * (M - K) ^ N * (-1) ^ K. We basically choose out of the M elements of the codomain, which of them we don't map anything to and then map the N elements of the domain in all the possible ways to the remainig (M - K) elements of the codomain. To count the number of derangements we can use again the principle of inclusion and exclusion. N! - AtLeastOneElementMappedCorrectly is the number of derangements. To count the number of ways we can map at least 1 element correctly, we use IEP in the following way: Sum(K <- 1, M) (M choose K) * (M - K)!. We basically choose at any step K out of the M elements to be mapped correctly and permute the remaining (M - K) elements. Complexity: O(M + M log MOD) = O(M)
