<?php

/*
 * Complete the 'beadOrnaments' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY b as parameter.
 */


$fp = fopen("php://stdin", "r");

const MOD = 1000000007;

fscanf($fp, "%d", $T);

while($T--){
    fscanf($fp, "%d", $n);
    
    $beads = explode(" ", trim(fgets($fp)));
    
    $result = total_ways_dp($beads);
    
    echo $result . "\n";
}

function total_ways_dp($beads) {
    global $n;
    
    $ALL = (1 << $n) - 1;
    $beads_sum = array_fill(0, 1 << $n, 0);
    $ways = array_fill(0, 1 << $n, 0);
  
    for ($mask = 1; $mask <= $ALL; ++$mask) {
        $k = 0;
        $m = bitcount($mask);
        $submask = (int)($mask - 1) & (int)$mask;
        
        while($k < $n && ((int)$mask & (1 << $k)) == 0) {
            ++ $k;
        }
        
        $beads_sum[$mask] = $beads_sum[$submask] + $beads[$k];
        
        if ($m == 1) {
            $ways[$mask] = power($beads[$k], $beads[$k] - 2);
        } else {
            for ($mask_a = (int)($mask - 1) & (int)$mask, $mask_b; $mask_a > 0; $mask_a = (int)($mask_a - 1) & (int)$mask) {
                $mask_b = $mask - $mask_a;
                $ways[$mask] = ($ways[$mask] + $ways[$mask_a] * $ways[$mask_b] % MOD * $beads_sum[$mask_a] * $beads_sum[$mask_b]) % MOD;
            }
            
            $ways[$mask] = $ways[$mask] * power(2 *($m - 1), MOD - 2) % MOD;
        }
    }
    
    return $ways[$ALL];
}

function power($a, $n) {
  if ($n < 0) {
    return power(power($a, MOD - 2), -$n);
  }
  
  if ($n == 0) {
    return 1;
  }
  
  if ($n == 1) {
    return $a;
  }
  
  $res = power($a, (int)($n/2));
  $res = $res * $res % MOD;
  
  if ((int)$n & 1) {
    $res = $res * $a % MOD;
  }
  
  return $res;
}

function bitcount($mask) {
    $cnt = 0;
    
    while($mask > 0) {
        $mask = (int)$mask & (int)($mask - 1);
        ++$cnt;
    }
    
    return $cnt;
}``