由于电信技术的发展，人人都可以通过手机互相联系。

有一位电信大佬最近想生产一大批手机，然而从生产线上一台一台地生产实在太慢了，于是他想出了一个办法 —— 让手机自我复制。

于是他给手机加上了一个内置的函数 fork()。手机的程序如果调用这个函数，那么手机会生产出一台完全一模一样的手机（包括程序运行状态），并且自己这台的函数返回值为 $1$，新手机的函数返回值为 $0$，然后两台手机都继续执行程序。（请注意黑体字内容）

初始时，只有一台手机。接着，大佬让手机计算形如这样的表达式：

fork() <op> fork() <op> ... <op> fork()

其中 <op> 是二元运算符，为 && 或者 || 中的一种。例如：

fork() && fork() || fork() && fork() && fork() || fork()

两个运算都是左结合的，且 && 的优先级比 || 高，所以上面的那个表达式相当于：

((fork() && fork()) || ((fork() && fork()) && fork())) || fork()

对于表达式 a && b，手机会先计算 a 的值，如果为 $0$ 那么不计算 b 的值（因为很重要所以说两遍，请注意这里不计算 b 的值），该表达式值为 $0$；否则计算 b 的值并将其值作为该表达式的值。

对于表达式 a || b，手机会先计算 a 的值，如果为 $1$ 那么不计算 b 的值（因为很重要所以说两遍，请注意这里不计算 b 的值），该表达式值为 $1$；否则计算 b 的值并将其值作为该表达式的值。

表达式计算完成后，大佬制造出了数量惊人的手机，人类终于叩开了指数级工业制造的大门。

一万万年后，一位考古学家调查了此次事件。他得到了大佬让手机计算的表达式。他想知道大佬当年究竟制造出了多少台手机。（包括初始的那台手机）

你可以参照样例解释来更好地理解题意。

输入格式

第一行一个正整数 $n$，表示表达式中的 fork() 的数量。

接下来一行 $n-1$ 个用空格隔开的字符串，每个字符串为 “&&” 或者 “||”，依次表示表达式中对应位置的运算符。

输出格式

一行，一个整数表示制造出的手机的数量，你只用输出答案对 $998244353$（$7\times 17\times 2^{23}+1$，一个质数）取模后的结果。

样例一

input

2
&&

output

3

explanation

共生产 $3$ 台手机，过程如下：

1. 第 $1$ 台手机开始计算 fork() && fork()。
2. 第 $1$ 台手机开始计算 fork()，产生了第 $2$ 台手机。
3. 第 $1$ 台和第 $2$ 台的 fork() 计算完成，第 $1$ 台返回 $1$，第 $2$ 台返回 $0$。
4. 第 $1$ 台手机由于 fork() 返回值为 $1$，开始计算 fork() && fork() 右边的 fork()，产生了第 $3$ 台手机。
5. 第 $2$ 台手机由于 fork() 返回值为 $0$，于是 fork() && fork() 值为 $0$（跳过右边的 fork 的计算），程序结束。
6. 第 $1$ 台和第 $3$ 台的 fork() 计算完成，第 $1$ 台返回 $1$，第 $3$ 台返回 $0$。
7. 第 $1$ 台手机由于 fork() 返回值为 $1$，于是 fork() && fork() 值为 $1$，程序结束。
8. 第 $3$ 台手机由于 fork() 返回值为 $0$，于是 fork() && fork() 值为 $0$，程序结束。

样例二

input

6
&& || && && ||

output

15

限制与约定

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载