We considerate the answer sequence, that's, the order we switch on the n lights.

Firstly, the sequence can be tot! cases, tot is the sum of off-lights.

Considerate the connected intervals of off-lights, such as [1,3], [5,7], [9,11] in sample 3, for each interval we have,

• Light can be chosen either it's in the left or the right of the interval. So we have 2^len - 1 orders to choose the len lights;

• The order of the sequence of the interval is limited to be 2^len - 1, but we calculated it with len! in tot!, len is the length of the interval.

Notice that if an interval has no on-light in it's left or right (such as [1,3] in sample 3), it just have one way to switch all lights on. So for these intervals, we don't multiply 2^len - 1 into the answer.

So it's easy to find the answer is , len_i is the length of the i-th interval.

By the way, because 10⁹ + 7 is a prime so we can calculate division by Euler's theorem.

// -> xue ying yu, shen ben bie D

Let's divide this queue into to 2 parts: 1... k and k + 1... n.

It's obvious that p_i ≤ k while i ≤ k, p_i > k while i > k.

So the answer to the part of p_{k + 1... n} is (n - k)^n - k.

Image a tree with k vertexes. The number of those trees is k^k - 2. (Cayley trees)

Choose a vertex to be root, there are k ways.

Set p_i = father_i in the tree. And for the root, set p_root = 1.

It's easy to find p_{1... k} satisfied the problem.

So answer is k^k - 1(n - k)^n - k.