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 2len - 1 orders to choose the len lights;
The order of the sequence of the interval is limited to be 2len - 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 2len - 1 into the answer.
So it's easy to find the answer is , leni is the length of the i-th interval.
By the way, because 109 + 7 is a prime so we can calculate division by Euler's theorem.
// -> xue ying yu, shen ben bie D
Is it true ? =)
Worked for me: 3486734
(I used Python’s built-in big-number arithmetics for powers and factorials, so I had to do
% 1000000007
just once.)