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