Teacher Mai 有 $n$ 个数字 $a_1, a_2, \dots, a_n$ 和 $n-1$ 个运算符（每个运算符为 '+'、'-' 或 '*' 中的一个）$op_1, op_2, \dots, op_{n-1}$，它们排列成 $a_1 \, op_1 \, a_2 \, op_2 \, a_3 \dots a_n$ 的形式。

他想要逐个消除数字。在第 $i$ 轮中，剩余 $n+1-i$ 个数字。他可以选择两个相邻的数字以及它们之间的运算符，将它们替换为通过该运算得到的新数字。经过 $n-1$ 轮后，只剩下一个数字。这个序列运算的结果即为最后剩下的数字。

他想知道所有不同运算序列的结果之和。当且仅当在某一轮中选择的数字不同时，两个运算序列被视为不同。

例如，对于 $1 + 4 * 6 - 8 * 3$，一种可能的运算序列是： $1 + 4 * 6 - 8 * 3 \to 1 + 4 * (-2) * 3 \to 1 + (-8) * 3 \to (-7) * 3 \to -21$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含一个整数 $n$ ($2 \le n \le 100$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)。 第三行包含一个长度为 $n-1$ 的字符串，由 '+'、'-' 和 '*' 组成，表示运算符序列。

输出格式

对于每个测试用例，输出结果对 $10^9 + 7$ 取模后的值。

样例

输入 1

2
3
3 2 1
-+
5
1 4 6 8 3
+*-*

输出 1

2
999999689