Statistics

Anu is a little child. His teacher asked him to solve the following problem:

There are n bins in a row. The bins are numbered 1 through n from the left to the right. There is also an infinite supply of balls of n distinct colors. Place exactly one ball into each bin, with the restriction that adjacent bins cannot contain balls of the same color. How many valid configurations of balls in bins are there?

Anu solved this problem correctly: "There are n * (n-1)^(n-1) valid configurations. Imagine that we are filling the bins from the left to the right. I have n possibilities for the color of the ball in the leftmost bin, and then (n-1) possibilities for each following ball, because I cannot use the color of the previous ball I placed."

However, Anu's teacher then tried to confuse Anu: "Sure, but what would happen if you were to fill the bins in a different order? Wouldn't that change the answer?"

Sadly, this time Anu got confused and answered incorrectly: "Yes, it would change the answer. For example, suppose that n = 3. If we fill the bins in the order {1, 2, 3}, we have 3*2*2 = 12 ways to fill them. However, suppose we fill them in the order {1, 3, 2}. Here we have 3 possibilities for the color of the ball in bin 1, then 3 possibilities for the color of the ball in bin 3, and then only 1 possibility for the color of the ball in bin 2 -- as there are already two forbidden colors when filling in bin 2. Thus, for this order there are only 3*3*1 = 9 ways to fill the bins."

Hopefully you can see where Anu made the mistake, but it is not really important for this problem.

In this problem we will focus on the (incorrect) method Anu used to count the number of ways to fill the bins, given the order in which to fill them. We can formally define this method as follows: Let P be a permutation of n bins. We will use f(P) to denote the value computed by Anu if the bins are filled in the order given by P. Anu will compute the value f(P) as follows: At the beginning, he sets f(P) to 1. Whenever he fills a bin, he multiplies f(P) by (n-x), where x is the number of neighboring bins that have already been filled. For example, if he has to put a ball into bin 7 in a situation where bins 6 and 8 already contain balls, he will multiply f(P) by (n-2).

You are given an int n. Anu has computed the value f(P) for each possible permutation P of numbers 1 through n. Let Z be the sum of the n factorial values Anu computed. Compute and return the value (Z modulo 1,000,000,007).