Knights

Problem Description

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?

Input

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.

Output

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.

Sample Input

2
2
0 0
3
0 1 0

Sample Output

Case #1: 500000004
Case #2: 250000002

Author

SYSU

Source

2016 Multi-University Training Contest 7