U387923 表达式的亿种可能性

有一个长度为 $2n-1$ 的表达式 $S(A_1,op_1,A_2,op_2,\cdots op_{n-1},A_n)$。你可以将他们以任意的运算顺序计算。显然，共有 $(n-1)!$ 中运算顺序。求以 $(n-1)!$ 种运算顺序计算的结果之和。答案对 $10^9+7$ 取整模。

第一行一个整数 $N$。 第二行 $n$ 个整数 $A_i$。 第三行 $n-1$ 个字符 $op_i$，保证 $op\in\{+,-,\times\}$。

一行一个整数，表示答案对 $10^9+7$ 取模的值。

对于所有数据，$1\leq N\leq100$，$1\leq A_i\leq10^9$，$op\in\{+,-,\times\}$。 样例解释：共有 $6$ 种计算顺序。 第一种情况：$1+2\to(1+2)-3\to((1+2)-3)\times4=0$。 第二种情况：$2-3\to1+(2-3)\to(1+(2-3))\times4=0$。 第三种情况：$2-3\to(2-3)\times4\to1+((2-3)\times4)=-3$。 第四种情况：$3\times4\to2-(3\times4)\to1+(2-(3\times4))=-9$。 第五种情况：$1+2\to3\times4\to(1+2)-(3\times4)=-9$。 第六种情况：$3\times4\to1+2\to(1+2)-(3\times4)=-9$。 $ans=(0+0-3-9-9-9)\bmod(10^9+7)=999999977$。