Knights

At the start of this game, there are N knights on a road of length N+1. The knights are numbered from 1 to N, and the ith knight stands i unit from the left end of the road.

When the game begins, each knight moves to left or right at the same speed. Whenever a knight reaches to the end of the road, he instantly changes his direction.

Whenever two knights meet, they fight until one loses, where each one of them wins in 50% possibility. Then the winner keeps moving in the direction he was moving before the fight, and the loser quits the game. The fighting time is very short and can be ignored.

The game continues until only one knight remains, and that knight is the winner.

Now, we know the moving direction of each knight initially. Can you calculate the possibility that Nth knight win the game?

The first line of the input gives the number of test cases T (T <= 10). In each test case, the first line is an integer N (1 <= N <= 1000). The second line contains N integers. The ith integer represents the ith knight’s moving direction, and 0 stands for left while 1 stands for right.

Each test case contains one line and one integer. Let’s assume the possibility be equal to the irreducible fraction P / Q. Print the value of $P\cdot Q^{-1}$ in the prime field of integers modulo $1\ 000\ 000\ 007 (10^9+7)$. It is guaranteed that this modulo does not divide Q, thus the number to be printed is well-defined.

2
2
0 0
3
0 1 0

Case #1: 500000004
Case #2: 250000002

SYSU

2016 Multi-University Training Contest 7