Problem Statement |
| | The king needs to distribute instructions to all his ministers. Since each minister requires a unique set of instructions, he writes a personalized letter for each minister and hands them off to his secretary to deliver.
Unfortunately, the king's secretary is a really careless fellow. He forgets that each minister has his own personalized letter, and he delivers a random letter to each minister instead. After he realizes his mistake, he begins to call the ministers one by one and asks them if they got the correct letter. So far, he has called K of the N ministers, and to his horror, none of the K ministers has received the correct letter.
The king is furious with his secretary, but he decides to give him one last chance to save his job. He asks the secretary the following question. In how many ways was it possible for him to distribute the letters so that the current situation would arise? In other words, how many different ways could the letters have been distributed such that a wrong letter went to each of the K ministers that has been called so far? Two ways are considered different if at least one minister gets a different letter. If the secretary can answer this question correctly, he can keep his job. Your job is to help the secretary by calculating the correct answer for him. Since the answer can be very large, return the answer modulo 1,000,000,007.
|
| |
Definition |
| | | Class: | CarelessSecretary | | Method: | howMany | | Parameters: | int, int | | Returns: | int | | Method signature: | int howMany(int N, int K) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | N will be between 1 and 1000, inclusive. |
| - | K will be between 1 and N, inclusive. |
| - | K will be between 1 and 12, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 1 | | There are two ministers, and one of them must not get his own letter. Therefore, the only possibility is that they get each other's letters. |
|
|
| 1) | |
| | | Returns: 4 | | The minister who must not get his own letter might get any of the two remaining letters. For each possibility, there are 2 ways to give the letters to the other ministers. Hence, the answer is 2*2 = 4.
|
|
|
| 2) | |
| | | Returns: 2 | | Three ministers, and none of them get their own letters. |
|
|
| 3) | |
| | |
| 4) | |
| | |
| 5) | |
| | |