UOJ Logo Universal Online Judge

UOJ

#113. 【UER #2】手机的生产

统计

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

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

于是他给手机加上了一个内置的函数 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

限制与约定

测试点编号 $n$的规模
1$n = 1$
2$n \leq 5$
3
4
5$n \leq 100$
6
7
8$n \leq 100000$
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载