반딧불이

Randal은 고차원 공간의 달인입니다. 그의 공간에 사는 모든 종은 그에게 반딧불이로 보입니다. 어느 날 그는 문제를 떠올렸지만 풀지 못했습니다. 당신이 이 문제를 풀 수 있습니까?

그는 n차원 초직육면체 부분공간 하나를 최소 개수의 반딧불이로 덮고 싶어 합니다. 공간의 변의 길이는 $p_1, p_2, \ldots, p_n$이며, 이 공간은 $\prod_{i=1}^{n} p_i$개의 초직육면체 단위로 이루어져 있습니다.

어떤 단위든 반딧불이 한 마리가 방문하면 덮인 것으로 봅니다. 각 반딧불이는 자신의 이동으로 여러 단위를 덮을 수 있습니다. 반딧불이가 좌표 $(x_1, x_2, \ldots, x_n)$ (단, $1 \le x_i \le p_i$)에 있을 때, 모든 $i$에 대해 $1 \le x_i \le y_i \le p_i$이고 $\sum_{i=1}^{n} |x_i - y_i| = 1$이면 좌표 $(y_1, y_2, \ldots, y_n)$으로 이동할 수 있습니다. 이동은 어느 위치에서 시작하고 끝나도 되며 횟수에도 제한이 없습니다. 다만 반딧불이 한 마리는 한 번만 이동합니다.

필요한 반딧불이의 최소 개수를 구하고, 그 값을 $10^9 + 7$로 나눈 나머지를 출력하세요.

첫 줄에 테스트 케이스의 개수 $T$가 주어집니다.

각 테스트 케이스는 두 줄로 이루어집니다. 첫 줄에는 공간의 차원 $n$이, 둘째 줄에는 공백으로 구분된 변의 길이 $p_1, p_2, \ldots, p_n$이 주어집니다.

제약: $1 \le T \le 2000$, $1 \le n \le 32$, $1 \le p_i \le 10^9$. $n > 8$인 테스트 케이스는 200개 이하, $n > 16$인 테스트 케이스는 20개 이하, $n > 24$인 테스트 케이스는 2개 이하입니다.

각 테스트 케이스마다 답을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력합니다.

첫 번째 테스트 케이스에서는 반딧불이 한 마리가 모든 단위를 덮을 수 있습니다.

두 번째 테스트 케이스에서는 최선의 방법 중 하나로, 두 번째 좌표가 같은 단위들을 반딧불이마다 하나씩 덮습니다. 이때 반딧불이는 세 마리가 필요합니다.