SP2963 PAINTBLC - Painting Blocks (Act II)

有 $n$ 个方块排成一行。你手中有 $k$ 种染料（$1 \le k \le 15$），其中第 $i$ 种染料最多可以用来给 $c_i$（$1 \le c_i \le 6$）个方块上色。假设所有 $c_i$ 的总和等于 $n$。你的任务是计算有多少种上色方法，要求相邻的方块不能涂成相同的颜色。

输入包含若干组测试数据。第一行是一个整数，表示测试数据的组数（不超过 2000）。对于每组测试数据，第一行有一个整数 $k$，接下来一行有 $k$ 个整数，分别是 $c_1, c_2, \ldots, c_k$。

对于每组测试数据，输出一个整数，即满足条件的上色方法数，并对 $1000000007$ 取模。 **本翻译由 AI 自动生成**