Expression 3
小青鱼有 n 个数 a1,a2,…,an 和 n−1 个运算符 op1,op2,…,opn−1。每个运算符都是 + 或 -,它们按下面的形式排列:
a1 op1 a2 op2 a3 ⋯ opn−1 an.
他希望逐步消去这些数。第 i 轮开始时,还剩 n+1−i 个数。他可以选择两个相邻的数,将这两个数及它们之间的运算符擦去,再把执行这次运算得到的新数放回原来的位置。
经过 n−1 轮后,只剩一个数。这个数称为该操作序列的结果。
请你求出所有不同操作序列的结果之和。答案可能很大,输出它对 998244353 取模的结果。当且仅当存在某一轮选择合并的两个数(在当时序列中的位置)不同,两个操作序列才视为不同。
输入格式
第一行包含一个整数 n,满足 2≤n≤2×105。
第二行包含 n 个整数 a1,a2,…,an,满足 0≤ai≤109。
第三行包含一个长度恰好为 n−1 的字符串,仅由 +、- 组成,表示原来的运算符序列。
输出格式
输出一个整数,表示所有不同操作序列的结果之和对 998244353 取模的结果。
样例 1 输入
4
9 1 4 1
-+-
样例 1 输出
46
样例 2 输入
5
1 2 3 4 5
+-+-
样例 2 输出
998244313
样例解释
样例 1 共有六种消去方式,以下每条箭头表示合并一对相邻的数与中间的运算符:
- $9-1+4-1\Rightarrow8+4-1\Rightarrow12-1\Rightarrow11$;
- 9−1+4−1⇒8+4−1⇒8+3⇒11;
- 9−1+4−1⇒9−5−1⇒4−1⇒3;
- 9−1+4−1⇒9−5−1⇒9−4⇒5;
- 9−1+4−1⇒9−1+3⇒8+3⇒11;
- 9−1+4−1⇒9−1+3⇒9−4⇒5。
因此答案为 11+11+3+5+11+5=46。