表达式

题目描述 你有�个数字�1 , �2 , …, �� 和� − 1 个运算符��1, ��2, …, ���−1 排成一行，形如 �1 ��1 �2 ��2 … ���−1 �� 。其中运算符是±*中的一个。

每次你会在剩余的数字里面，选出两个相邻的数字，根据它们之间的运算符计算出 结果，然后把这两个数和这个运算符替换成算出来的结果。这样进行� − 1 轮之后 只剩一个数字。

你想知道对于所有操作的方法，得到的最后的结果的和。两个操作的方法相同，当 且仅当每一次操作两种操作方法选的数字位置都一样。

输出答案对109 + 7 取模的结果，如果余数是负数，把它加上109 + 7 后输出。

输入格式 第一行，一个整数�。

接下来一行，�个整数，表示�1 , �2 , …, �� 。

接下来一行，一个长度为� − 1 的字符串，每个运算符是±*中的一个。

输出格式 一行，一个整数表示答案。

样例输入 1 3 3 2 1 -+

样例输出 2 5 1 4 6 8 3 +-

样例输出 2 999999689

样例输入 3 10 517974382 763433648 185159600 390253537 104798220 734850655 170422025 7 48232829 820177910 110047331 -±–+*

样例输出 3 123105432 数据规模 共 10 组数据。

测试点 1,2 满足� ≤ 10。

测试点 3 满足运算符只有+。

测试点 4,5 满足运算符只有±。

测试点 6,7 满足运算符只有+*。

对于所有数据，满足 2 ≤ � ≤ 500,1 ≤ �� ≤ 109 。