Problem Background

This problem is the first question in the second public competition of StOI, StOI Round2.

Note: If the number is a multi-digit number, it will not be split. By LHQing, 14:09

:)

Problem Description

Given an expression consisting only of digits, +, and *, calculate the sum of the values of all its sub-expressions modulo $998,244,353$.

A sub-expression is defined as a continuous sequence of digits and the operators within it.

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

Input Format

The first line contains a positive integer $n$, representing the number of digits in the expression.

The next line is the expression consisting of $n$ positive integers and $n-1$ operators, with spaces separating the digits and operators.

Output Format

Output a single number, representing the final answer.

Sample Input and Output

Sample Input #1

3
1 + 2 * 3

Sample Output #1

22

Sample Input #2

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

Sample Output #2

414

Sample Input #3

3
16 + 750 + 7

Sample Output #3

3069

Notes

Sample Explanation

The given expression has six sub-expressions:
$1$, $2$, $3$, $1+2$, $2 \times 3$, $1+2 \times 3$, with values $1$, $2$, $3$, $3$, $6$, $7$ respectively, summing up to $22$.

Data Range

For $20\%$ of the data: $1 \leq n \leq 1000$.
For another $20\%$ of the data: No + exists.
For another $20\%$ of the data: Only one + exists.
For another $20\%$ of the data: Only one * exists.
For $100\%$ of the data: $1 \leq n \leq 10^{5}$, all numbers are no greater than $10^{9}$, and the operators include only + and *.

见题面 Input 部分

见题面 Output 部分