Let’s restate the problem.

• Find the output of the following program when the string \(S\) is input.

S = input()
MOD = 998244353
ans = 0
for i in range(len(S)):
    for j in range(i, len(S)):
        if S[i].isdigit() and S[j].isdigit():
            ans += eval(S[i : j + 1])
print(ans % MOD)

• Main constraints:
  • \(|S| \leq 10^6\)
  • Each character of \(S\) is one of 123456789+*.

---

If there are just digits

Let’s assume all characters in \(S\) are digits. For example, let \(S =\) 1234. The cases where the digit 2 contributes to \(\mathrm{eval}(S_{i..j})\) are as follows:

• \(12 = 1 \times 10 + \underline{2 \times 1}\)
• \(123 = 1 \times 100 + \underline{2 \times 10} + 3 \times 1\)
• \(1234 = 1 \times 1000 + \underline{2 \times 100} + 3 \times 10 + 4 \times 1\)
• \(2 = \underline{2 \times 1}\)
• \(23 = \underline{2 \times 10} + 3 \times 1\)
• \(234 = \underline{2 \times 100} + 3 \times 10 + 4 \times 1\)

In total, the digit 2 is added to the answer \(222\) times. Considering the other digits similarly, we see that the answer is \(1 \times 1111 + 2 \times 222 + 3 \times 33 + 4 \times 4\).

Note that we can independently consider the left and right sides with respect to each digit. For example, if \(S =\) 12, the digit 2 is added to the answer twice, and if \(S =\) 234, it’s added \(111\) times. For \(S =\) 1234, the number of times is the product of these.

Digits and +

Let’s assume all characters in \(S\) are digits or +. For example, let \(S =\) 99+1234+999. The cases where the digit 2 contributes to \(\mathrm{eval}(S_{i..j})\) are as follows:

\(\mathrm{eval}(S_{i..j})\)	：	Contribution count
\(99+12\)	：	\(1\)
\(99+123\)	：	\(10\)
\(99+1234\)	：	\(100\)
\(99+1234+9\)	：	\(100\)
\(99+1234+99\)	：	\(100\)
\(99+1234+999\)	：	\(100\)
\(9+12\)	：	\(1\)
\(9+123\)	：	\(10\)
\(9+1234\)	：	\(100\)
\(9+1234+9\)	：	\(100\)
\(9+1234+99\)	：	\(100\)
\(9+1234+999\)	：	\(100\)
\(12\)	：	\(1\)
\(123\)	：	\(10\)
\(1234\)	：	\(100\)
\(1234+9\)	：	\(100\)
\(1234+99\)	：	\(100\)
\(1234+999\)	：	\(100\)
\(2\)	：	\(1\)
\(23\)	：	\(10\)
\(234\)	：	\(100\)
\(234+9\)	：	\(100\)
\(234+99\)	：	\(100\)
\(234+999\)	：	\(100\)

In total, the digit 2 is added to the answer \(4 \times 411\) times. Considering the other digits similarly, we can find the answer.

Note again that we can independently consider the left and right sides with respect to each digit. For example, if \(S =\) 99+12, the digit 2 is added to the answer four times, and if \(S =\) 234+999, it’s added \(411\) times. For \(S =\) 99+1234+999, the number of times is the product of these.

Digits, +, and *

Let’s assume all characters in \(S\) are digits, +, or * (the original problem). With multiplication added, we need to revise our previous approach.

For example, the answer for \(S =\) 2*3 is \(2 + 2 \times 3 + 3\), but if we consider the contributions of 2 and 3 as before and add them up, we would count \(2 \times 3\) twice. Here, let’s treat the result of multiplication as a contribution from the rightmost element. For \(S =\) 2*3, we consider that 3 is added twice for \(2 \times 3\), so \(2\) is added to the answer once, while \(3\) is added \(2 + 1 = 3\) times.

With this approach, we can perform the same calculations as before. For example, let \(S =\) 99+345*456*567*12. The cases where the digit 2 contributes to \(\mathrm{eval}(S_{i..j})\) are as follows:

$\mathrm{eval}(S_{i..j})$	：	Contribution count
$99+345\times456\times567\times12$	：	$345\times456\times567$
$9+345\times456\times567\times12$	：	$345\times456\times567$
$345\times456\times567\times12$	：	$345\times456\times567$
$45\times456\times567\times12$	：	$45\times456\times567$
$5\times456\times567\times12$	：	$5\times456\times567$
$456\times567\times12$	：	$456\times567$
$56\times567\times12$	：	$56\times567$
$6\times567\times12$	：	$6\times567$
$567\times12$	：	$567$
$67\times12$	：	$67$
$7\times12$	：	$7$
$12$	：	$1$
$2$	：	$1$

In total, the digit 2 is added to the answer \(2 \times 345 \times 456 \times 567 + (345 + 45 + 5) \times 456 \times 567 + (456 + 56 + 6) \times 567 + (567 + 67 + 7) + 2\) times. For digits other than the last in \(S\), we can consider the left and right sides independently as before. Here, since we treat the result of multiplication as a contribution from the rightmost element, if the first operator to the right of a digit is *, we do not consider cases that span that *.

By avoiding repeated calculations, we can compute the answer in linear time.

Sample implementation (Python)

S = input()
MOD = 998244353

p10 = [1] * (len(S) + 1)
for i in range(len(S)):
    p10[i + 1] = p10[i] * 10 % MOD
q10 = [0] * (len(S) + 1)
for i in range(len(S)):
    q10[i + 1] = (q10[i] + p10[i]) % MOD

ans = 0
sofar, remain = 0, len(list(filter(lambda c: c.isdigit(), S)))
for t in S.split("+"):
    p, q = 1, 0
    ts = t.split("*")
    for i in range(len(ts)):
        u = ts[i]
        remain -= len(u)
        v, w = 0, 0
        for j in range(len(u) - 1, -1, -1):
            l = j + 1 + q + p * sofar
            r = q10[len(u) - j]
            if i == len(ts) - 1:
                r += p10[len(u) - 1 - j] * remain
            ans = (ans + int(u[j]) * l * r) % MOD
            v = (v + int(u[j]) * p10[len(u) - 1 - j]) % MOD
            w = (w + v) % MOD
        p = p * v % MOD
        q = (q * v + w) % MOD
    sofar += len(t) - t.count("*")
print(ans)