Background

This problem is the first problem of the second open contest of StOI, StOI Round2.

Note: If this number has multiple digits, it will not be split apart. By LHQing, 14:09.

:)

Problem Description

Given an expression consisting only of digits, +, and *, find the sum of the values of all its subexpressions, modulo $998,244,353$.

A subexpression of an expression is defined as an expression formed by a consecutive segment of numbers and the operators between them.

If you still cannot understand, you can refer to the sample explanation.

Input Format

The first line contains a positive integer $n$, which denotes the number of numbers in the expression.

The next line contains the expression consisting of $n$ positive integers and $n - 1$ operators, with spaces between numbers and operators.

Output Format

Output one number, which is the final answer.

3
1 + 2 * 3

22

6
1 * 1 * 4 * 5 * 1 * 4

414

3
16 + 750 + 7

3069

Hint

Sample Explanation

The given expression has a total of six subexpressions: $1$, $2$, $3$, $1+2$, $2 \times 3$, $1+2 \times 3$. Their values are $1$, $2$, $3$, $3$, $6$, $7$, and the sum is $22$.

Constraints

For $20\%$ of the testdata: $1 \leq n \leq 1000$.
For another $20\%$ of the testdata: there is no +.
For another $20\%$ of the testdata: there is only one +.
For another $20\%$ of the testdata: there is only one *.
For $100\%$ of the testdata: $1 \leq n \leq 10^{5}$, all numbers are at most $10^{9}$, and the operators only include + and *.

Output Format

Translated by ChatGPT 5