Problem #61
Derangements
There are n people and n houses, such that every person owns exactly one distinct house. Out of these n people, k people are special (k \lt = n). You have to send every person to exactly one house such that no house has more than one person, and no special person goes to his own house. Let S(n,k) be the number of ways of doing this. Find the value of S(654321,123456). Give your answer \mod 10^9 + 7.