Little Cyan Fish 有 $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$ 轮后，只剩下一个数字。这一系列运算的结果即为最后剩下的那个数字。

他想知道所有不同运算序列的结果之和。由于结果可能很大，请输出其对 $998\,244\,353$ 取模的结果。当且仅当他在某一轮中选择了不同的数字进行运算时，两个运算序列被视为不同。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 2 \times 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)。

第三行包含一个长度为 $n-1$ 的字符串，由 “+” 和 “-” 组成，表示运算符序列。

输出格式

输出答案对 $998\,244\,353$ 取模的结果。

样例

输入 1

4
9 1 4 1
-+-

输出 1

46

输入 2

5
1 2 3 4 5
+-+-

输出 2

998244313

说明

在第一个样例中，有六种可能的擦除数字的方式：

• $9 - 1 + 4 - 1 \implies 8 + 4 - 1 \implies 12 - 1 \implies 11$
• $9 - 1 + 4 - 1 \implies 8 + 4 - 1 \implies 8 + 3 \implies 11$
• $9 - 1 + 4 - 1 \implies 9 - 5 - 1 \implies 4 - 1 \implies 3$
• $9 - 1 + 4 - 1 \implies 9 - 5 - 1 \implies 9 - 4 \implies 5$
• $9 - 1 + 4 - 1 \implies 9 - 1 + 3 \implies 8 + 3 \implies 11$
• $9 - 1 + 4 - 1 \implies 9 - 1 + 3 \implies 9 - 4 \implies 5$

因此答案为 $11 + 11 + 3 + 5 + 11 + 5 = 46$。