← 返回题目列表

AtCoder · jag2017summer_day1_e

E. 向量表达

中文机器翻译题面 查看原题

問題文

以BNF表示的载体表达如下 已给出 S ,请计算。

<expr> ::= <number> | "("<expr>"*"<expr>")" | "("<vector>"*"<vector>")"
<vector> ::= "("<expr>","<expr>")" | "("<expr>"*"<vector>")" | "("<vector>"*"<expr>")"
<number> ::= <digit> | <number><digit>
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

<expr> 的值是一个整数(标量),<vector> 的值是一个二维向量。 操作员 本题中 * 的含义如下。

  • <expr> Case:表示整数的乘积。
  • <vector> 对于两者:表示向量的内积。
  • <expr> 和 <vector> :表示向量的标量乘法。

然而,答案可能非常大,所以 请输出除以998244353 后的余数。

制約

  • 1≦|S|≦10^5
  • S 是问题文本中的 BNF。 它是表示为 <expr> 的表达式。

入力

输入将以以下格式从标准输入给出。

S

出力

公式的计算结果 998244353 后的余数。


入力例 1

((1,2)*(3,4))

出力例 1

11

矢量 (1,2) 和矢量 计算 (3,4) 的内积 1*3 + 2*4 = 11 。


入力例 2

((((1*2),3)*4)*(((5,6)*(7,8))*(9,10)))

出力例 2

15936

入力例 3

0000000000099824435399824435399824435399824435399824435398

出力例 3

98