Expression Sum
Source: aizu

Expression Sum
Problem Statement

You are given a string $S$. Each character in $S$ is one of 0123456789+()?.

Let $T$ be a string formed by replacing each ? in $S$ with one of 0123456789+(). Define $eval(T)$ as follows:

If $T$ is a valid expression, then it is the value obtained by evaluating $T$ as an expression.
If $T$ is not a valid expression, then it is $0$.

Compute the sum of $eval(T)$ for all possible ways to replace each ? in $S$ with one of 0123456789+(), and output the result modulo $998,244,353$.

A valid expression is defined by the following BNF:

<expression> ::= <expression> "+" <primary> | <primary>
<primary> ::= "(" <expression> ")" | <number>
<number> ::= <nonzero-digit> <number-sub> | <digit>
<number-sub> ::= <number-sub> <digit> | <digit>
<digit> ::= "0" | <nonzero-digit>
<nonzero-digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Input

The input is given in the following format:

$S$  

$1 \leq |S| \leq 3,000$
Each character of $S$ is one of 0123456789+()?.
Output

Output the answer.

Sample Input 1
?1?

Sample Output 1
46306

Sample Input 2
20???0+2??

Sample Output 2
651059511


C++ solution:
// AOJ #3627 Expression Sum
// 2025.4.19

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;

int add(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
int mul(long long a, long long b){ return int(a * b % MOD); }

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    string S;
    cin >> S;
    int n = S.size();

    vector<int> v0(n+2,0), s0(n+2,0),
                v1(n+2,0), s1(n+2,0), p1(n+2,0),
                v2(n+2,0), s2(n+2,0);
    vector<int> u0(n+2,0), t0(n+2,0),
                u1(n+2,0), t1(n+2,0), q1(n+2,0),
                u2(n+2,0), t2(n+2,0);

    v0[0] = 1;

    for(int i = 0; i < n; i++){
        fill(u0.begin(), u0.end(), 0);
        fill(t0.begin(), t0.end(), 0);
        fill(u1.begin(), u1.end(), 0);
        fill(t1.begin(), t1.end(), 0);
        fill(q1.begin(), q1.end(), 0);
        fill(u2.begin(), u2.end(), 0);
        fill(t2.begin(), t2.end(), 0);

        char c = S[i];
        for(int b = 0; b <= n; b++){
            int c0 = v0[b], e0 = s0[b];
            int c1 = v1[b], e1 = s1[b], w1 = p1[b];
            int c2 = v2[b], e2 = s2[b];

            if(c=='(' || c=='?'){
                if(b+1 <= n){
                    u0[b+1] = add(u0[b+1], c0);
                    t0[b+1] = add(t0[b+1], e0);
                }
            }
            if(c=='?' || isdigit(c)){
                bool ok0 = (c=='?' || c=='0');
                if(ok0){
                    u2[b] = add(u2[b], c0);
                    t2[b] = add(t2[b], e0);
                }
                int cnt9 = 0, sum9 = 0;
                if(c=='?') cnt9 = 9, sum9 = 45;
                else if(c>='1' && c<='9') cnt9 = 1, sum9 = c - '0';
                if(cnt9){
                    u1[b] = add(u1[b], mul(c0, cnt9));
                    t1[b] = add(t1[b], mul(e0, cnt9));
                    q1[b] = add(q1[b], mul(c0, sum9));
                }
            }

            if(c1){
                if(c=='?' || isdigit(c)){
                    int cntD=0, sumD=0;
                    if(c=='?'){ cntD=10; sumD=45; }
                    else{ cntD=1; sumD=c-'0'; }
                    u1[b] = add(u1[b], mul(c1, cntD));
                    t1[b] = add(t1[b], mul(e1, cntD));
                    q1[b] = add(q1[b],
                        add( mul(mul(w1,10), cntD),
                             mul(c1, sumD) ));
                }
                int totEndC = add(e1, w1);
                if(c=='+' || c=='?'){
                    u0[b] = add(u0[b], c1);
                    t0[b] = add(t0[b], totEndC);
                }
                if(b>0 && (c==')' || c=='?')){
                    u2[b-1] = add(u2[b-1], c1);
                    t2[b-1] = add(t2[b-1], totEndC);
                }
            }

            if(c2){
                if(c=='+' || c=='?'){
                    u0[b] = add(u0[b], c2);
                    t0[b] = add(t0[b], e2);
                }
                if(b>0 && (c==')' || c=='?')){
                    u2[b-1] = add(u2[b-1], c2);
                    t2[b-1] = add(t2[b-1], e2);
                }
            }
        }

        v0.swap(u0); s0.swap(t0);
        v1.swap(u1); s1.swap(t1); p1.swap(q1);
        v2.swap(u2); s2.swap(t2);
    }

    vector<int> final2(n+2,0), finalS(n+2,0);
    for(int b=0;b<=n;b++){
        final2[b] = add(final2[b], v2[b]);
        finalS[b] = add(finalS[b], s2[b]);
        if(v1[b]){
            final2[b] = add(final2[b], v1[b]);
            finalS[b] = add(finalS[b], add(s1[b], p1[b]));
        }
    }

    int ans = finalS[0];
    cout << ans << endl;
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD = 998244353

func add(a, b int) int {
	a += b
	if a >= MOD {
		a -= MOD
	}
	return a
}

func mul(a, b int) int {
	return int(int64(a) * int64(b) % MOD)
}

func isDigit(c byte) bool {
	return c >= '0' && c <= '9'
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	S := scanner.Text()
	n := len(S)

	if n == 0 {
		fmt.Println(0)
		return
	}

	// Initialize all DP arrays
	v0 := make([]int, n+2)
	s0 := make([]int, n+2)
	v1 := make([]int, n+2)
	s1 := make([]int, n+2)
	p1 := make([]int, n+2)
	v2 := make([]int, n+2)
	s2 := make([]int, n+2)

	u0 := make([]int, n+2)
	t0 := make([]int, n+2)
	u1 := make([]int, n+2)
	t1 := make([]int, n+2)
	q1 := make([]int, n+2)
	u2 := make([]int, n+2)
	t2 := make([]int, n+2)

	v0[0] = 1

	for i := 0; i < n; i++ {
		c := S[i]

		// Clear temporary arrays
		for j := 0; j <= n+1; j++ {
			u0[j] = 0
			t0[j] = 0
			u1[j] = 0
			t1[j] = 0
			q1[j] = 0
			u2[j] = 0
			t2[j] = 0
		}

		for b := 0; b <= n; b++ {
			c0 := v0[b]
			e0 := s0[b]
			c1 := v1[b]
			e1 := s1[b]
			w1 := p1[b]
			c2 := v2[b]
			e2 := s2[b]

			if c == '(' || c == '?' {
				if b+1 <= n {
					u0[b+1] = add(u0[b+1], c0)
					t0[b+1] = add(t0[b+1], e0)
				}
			}
			if c == '?' || isDigit(c) {
				ok0 := (c == '?' || c == '0')
				if ok0 {
					u2[b] = add(u2[b], c0)
					t2[b] = add(t2[b], e0)
				}
				var cnt9, sum9 int
				if c == '?' {
					cnt9 = 9
					sum9 = 45
				} else if c >= '1' && c <= '9' {
					cnt9 = 1
					sum9 = int(c - '0')
				}
				if cnt9 > 0 {
					u1[b] = add(u1[b], mul(c0, cnt9))
					t1[b] = add(t1[b], mul(e0, cnt9))
					q1[b] = add(q1[b], mul(c0, sum9))
				}
			}

			if c1 > 0 {
				if c == '?' || isDigit(c) {
					var cntD, sumD int
					if c == '?' {
						cntD = 10
						sumD = 45
					} else {
						cntD = 1
						sumD = int(c - '0')
					}
					u1[b] = add(u1[b], mul(c1, cntD))
					t1[b] = add(t1[b], mul(e1, cntD))
					q1[b] = add(q1[b],
						add(mul(mul(w1, 10), cntD),
							mul(c1, sumD)))
				}
				totEndC := add(e1, w1)
				if c == '+' || c == '?' {
					u0[b] = add(u0[b], c1)
					t0[b] = add(t0[b], totEndC)
				}
				if b > 0 && (c == ')' || c == '?') {
					u2[b-1] = add(u2[b-1], c1)
					t2[b-1] = add(t2[b-1], totEndC)
				}
			}

			if c2 > 0 {
				if c == '+' || c == '?' {
					u0[b] = add(u0[b], c2)
					t0[b] = add(t0[b], e2)
				}
				if b > 0 && (c == ')' || c == '?') {
					u2[b-1] = add(u2[b-1], c2)
					t2[b-1] = add(t2[b-1], e2)
				}
			}
		}

		// Swap arrays for next iteration
		v0, u0 = u0, v0
		s0, t0 = t0, s0
		v1, u1 = u1, v1
		s1, t1 = t1, s1
		p1, q1 = q1, p1
		v2, u2 = u2, v2
		s2, t2 = t2, s2
	}

	// Collect final results
	final2 := make([]int, n+2)
	finalS := make([]int, n+2)
	for b := 0; b <= n; b++ {
		final2[b] = add(final2[b], v2[b])
		finalS[b] = add(finalS[b], s2[b])
		if v1[b] > 0 {
			final2[b] = add(final2[b], v1[b])
			finalS[b] = add(finalS[b], add(s1[b], p1[b]))
		}
	}

	ans := finalS[0]
	fmt.Println(ans)
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 998244353;

    static int add(int a, int b) {
        a += b;
        if (a >= MOD) a -= MOD;
        return a;
    }

    static int mul(long a, long b) {
        return (int) ((a * b) % MOD);
    }

    static boolean isDigit(char c) {
        return c >= '0' && c <= '9';
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        int n = S.length();

        // DP states:
        // v0: expressions that can continue with '+' or start a new primary
        // v1: numbers being formed (with p1 tracking the current numeric value)
        // v2: expressions that can be closed with ')'
        int[] v0 = new int[n+2], s0 = new int[n+2];
        int[] v1 = new int[n+2], s1 = new int[n+2], p1 = new int[n+2];
        int[] v2 = new int[n+2], s2 = new int[n+2];
        
        // Temporary arrays for updates
        int[] u0 = new int[n+2], t0 = new int[n+2];
        int[] u1 = new int[n+2], t1 = new int[n+2], q1 = new int[n+2];
        int[] u2 = new int[n+2], t2 = new int[n+2];

        // Initial state: empty expression with balance 0
        v0[0] = 1;

        for (int i = 0; i < n; i++) {
            // Clear temporary arrays
            Arrays.fill(u0, 0);
            Arrays.fill(t0, 0);
            Arrays.fill(u1, 0);
            Arrays.fill(t1, 0);
            Arrays.fill(q1, 0);
            Arrays.fill(u2, 0);
            Arrays.fill(t2, 0);

            char c = S.charAt(i);
            for (int b = 0; b <= n; b++) {
                int c0 = v0[b], e0 = s0[b];
                int c1 = v1[b], e1 = s1[b], w1 = p1[b];
                int c2 = v2[b], e2 = s2[b];

                // Handle '(' or '?'
                if (c == '(' || c == '?') {
                    if (b + 1 <= n) {
                        u0[b+1] = add(u0[b+1], c0);
                        t0[b+1] = add(t0[b+1], e0);
                    }
                }

                // Handle digits or '?'
                if (c == '?' || isDigit(c)) {
                    boolean ok0 = (c == '?' || c == '0');
                    if (ok0) {
                        u2[b] = add(u2[b], c0);
                        t2[b] = add(t2[b], e0);
                    }
                    int cnt9 = 0, sum9 = 0;
                    if (c == '?') {
                        cnt9 = 9;
                        sum9 = 45;
                    } else if (c >= '1' && c <= '9') {
                        cnt9 = 1;
                        sum9 = c - '0';
                    }
                    if (cnt9 != 0) {
                        u1[b] = add(u1[b], mul(c0, cnt9));
                        t1[b] = add(t1[b], mul(e0, cnt9));
                        q1[b] = add(q1[b], mul(c0, sum9));
                    }
                }

                // Handle numbers (v1)
                if (c1 != 0) {
                    if (c == '?' || isDigit(c)) {
                        int cntD = 0, sumD = 0;
                        if (c == '?') {
                            cntD = 10;
                            sumD = 45;
                        } else {
                            cntD = 1;
                            sumD = c - '0';
                        }
                        u1[b] = add(u1[b], mul(c1, cntD));
                        t1[b] = add(t1[b], mul(e1, cntD));
                        q1[b] = add(q1[b], 
                            add(mul(mul(w1, 10), cntD), 
                                mul(c1, sumD)));
                    }
                    int totEndC = add(e1, w1);
                    if (c == '+' || c == '?') {
                        u0[b] = add(u0[b], c1);
                        t0[b] = add(t0[b], totEndC);
                    }
                    if (b > 0 && (c == ')' || c == '?')) {
                        u2[b-1] = add(u2[b-1], c1);
                        t2[b-1] = add(t2[b-1], totEndC);
                    }
                }

                // Handle expressions that can be closed (v2)
                if (c2 != 0) {
                    if (c == '+' || c == '?') {
                        u0[b] = add(u0[b], c2);
                        t0[b] = add(t0[b], e2);
                    }
                    if (b > 0 && (c == ')' || c == '?')) {
                        u2[b-1] = add(u2[b-1], c2);
                        t2[b-1] = add(t2[b-1], e2);
                    }
                }
            }

            // Swap arrays for next iteration
            int[] temp;
            temp = v0; v0 = u0; u0 = temp;
            temp = s0; s0 = t0; t0 = temp;
            temp = v1; v1 = u1; u1 = temp;
            temp = s1; s1 = t1; t1 = temp;
            temp = p1; p1 = q1; q1 = temp;
            temp = v2; v2 = u2; u2 = temp;
            temp = s2; s2 = t2; t2 = temp;
        }

        // Calculate final answer by combining all valid expressions
        int ans = 0;
        // Add valid numbers
        if (v1[0] != 0) {
            ans = add(ans, add(s1[0], p1[0]));
        }
        // Add valid expressions that can be closed
        if (v2[0] != 0) {
            ans = add(ans, s2[0]);
        }

        System.out.println(ans);
    }
}

JavaScript solution:
const MOD = 998244353;

function add(a, b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

function mul(a, b) {
    return Number((BigInt(a) * BigInt(b)) % BigInt(MOD));
}

function solve() {
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    rl.on('line', (input) => {
        const S = input.trim();
        const n = S.length;

        let v0 = new Array(n + 2).fill(0);
        let s0 = new Array(n + 2).fill(0);
        let v1 = new Array(n + 2).fill(0);
        let s1 = new Array(n + 2).fill(0);
        let p1 = new Array(n + 2).fill(0);
        let v2 = new Array(n + 2).fill(0);
        let s2 = new Array(n + 2).fill(0);

        v0[0] = 1;

        for (let i = 0; i < n; i++) {
            let u0 = new Array(n + 2).fill(0);
            let t0 = new Array(n + 2).fill(0);
            let u1 = new Array(n + 2).fill(0);
            let t1 = new Array(n + 2).fill(0);
            let q1 = new Array(n + 2).fill(0);
            let u2 = new Array(n + 2).fill(0);
            let t2 = new Array(n + 2).fill(0);

            const c = S[i];
            for (let b = 0; b <= n; b++) {
                const c0 = v0[b], e0 = s0[b];
                const c1 = v1[b], e1 = s1[b], w1 = p1[b];
                const c2 = v2[b], e2 = s2[b];

                if (c === '(' || c === '?') {
                    if (b + 1 <= n) {
                        u0[b + 1] = add(u0[b + 1], c0);
                        t0[b + 1] = add(t0[b + 1], e0);
                    }
                }
                if (c === '?' || (c >= '0' && c <= '9')) {
                    const ok0 = (c === '?' || c === '0');
                    if (ok0) {
                        u2[b] = add(u2[b], c0);
                        t2[b] = add(t2[b], e0);
                    }
                    let cnt9 = 0, sum9 = 0;
                    if (c === '?') {
                        cnt9 = 9;
                        sum9 = 45;
                    } else if (c >= '1' && c <= '9') {
                        cnt9 = 1;
                        sum9 = c.charCodeAt(0) - '0'.charCodeAt(0);
                    }
                    if (cnt9 > 0) {
                        u1[b] = add(u1[b], mul(c0, cnt9));
                        t1[b] = add(t1[b], mul(e0, cnt9));
                        q1[b] = add(q1[b], mul(c0, sum9));
                    }
                }

                if (c1 > 0) {
                    if (c === '?' || (c >= '0' && c <= '9')) {
                        let cntD = 0, sumD = 0;
                        if (c === '?') {
                            cntD = 10;
                            sumD = 45;
                        } else {
                            cntD = 1;
                            sumD = c.charCodeAt(0) - '0'.charCodeAt(0);
                        }
                        u1[b] = add(u1[b], mul(c1, cntD));
                        t1[b] = add(t1[b], mul(e1, cntD));
                        q1[b] = add(q1[b], add(mul(mul(w1, 10), cntD), mul(c1, sumD)));
                    }
                    const totEndC = add(e1, w1);
                    if (c === '+' || c === '?') {
                        u0[b] = add(u0[b], c1);
                        t0[b] = add(t0[b], totEndC);
                    }
                    if (b > 0 && (c === ')' || c === '?')) {
                        u2[b - 1] = add(u2[b - 1], c1);
                        t2[b - 1] = add(t2[b - 1], totEndC);
                    }
                }

                if (c2 > 0) {
                    if (c === '+' || c === '?') {
                        u0[b] = add(u0[b], c2);
                        t0[b] = add(t0[b], e2);
                    }
                    if (b > 0 && (c === ')' || c === '?')) {
                        u2[b - 1] = add(u2[b - 1], c2);
                        t2[b - 1] = add(t2[b - 1], e2);
                    }
                }
            }

            v0 = u0;
            s0 = t0;
            v1 = u1;
            s1 = t1;
            p1 = q1;
            v2 = u2;
            s2 = t2;
        }

        let final2 = new Array(n + 2).fill(0);
        let finalS = new Array(n + 2).fill(0);
        for (let b = 0; b <= n; b++) {
            final2[b] = add(final2[b], v2[b]);
            finalS[b] = add(finalS[b], s2[b]);
            if (v1[b] > 0) {
                final2[b] = add(final2[b], v1[b]);
                finalS[b] = add(finalS[b], add(s1[b], p1[b]));
            }
        }

        console.log(finalS[0]);
        rl.close();
    });
}

solve();

Python solution:
import sys
MOD = 998244353

def add(a, b):
    a += b
    if a >= MOD:
        a -= MOD
    return a

def mul(a, b):
    return (a * b) % MOD

def solve():
    S = sys.stdin.readline().strip()
    n = len(S)
    
    # Initialize DP arrays
    v0 = [0] * (n + 2)
    s0 = [0] * (n + 2)
    v1 = [0] * (n + 2)
    s1 = [0] * (n + 2)
    p1 = [0] * (n + 2)
    v2 = [0] * (n + 2)
    s2 = [0] * (n + 2)
    
    v0[0] = 1
    
    for i in range(n):
        u0 = [0] * (n + 2)
        t0 = [0] * (n + 2)
        u1 = [0] * (n + 2)
        t1 = [0] * (n + 2)
        q1 = [0] * (n + 2)
        u2 = [0] * (n + 2)
        t2 = [0] * (n + 2)
        
        c = S[i]
        for b in range(n + 1):
            c0 = v0[b]
            e0 = s0[b]
            c1 = v1[b]
            e1 = s1[b]
            w1 = p1[b]
            c2 = v2[b]
            e2 = s2[b]
            
            if c == '(' or c == '?':
                if b + 1 <= n:
                    u0[b + 1] = add(u0[b + 1], c0)
                    t0[b + 1] = add(t0[b + 1], e0)
            
            if c == '?' or c.isdigit():
                ok0 = (c == '?' or c == '0')
                if ok0:
                    u2[b] = add(u2[b], c0)
                    t2[b] = add(t2[b], e0)
                
                cnt9 = 0
                sum9 = 0
                if c == '?':
                    cnt9 = 9
                    sum9 = 45
                elif c >= '1' and c <= '9':
                    cnt9 = 1
                    sum9 = ord(c) - ord('0')
                if cnt9 > 0:
                    u1[b] = add(u1[b], mul(c0, cnt9))
                    t1[b] = add(t1[b], mul(e0, cnt9))
                    q1[b] = add(q1[b], mul(c0, sum9))
            
            if c1 > 0:
                if c == '?' or c.isdigit():
                    cntD = 0
                    sumD = 0
                    if c == '?':
                        cntD = 10
                        sumD = 45
                    else:
                        cntD = 1
                        sumD = ord(c) - ord('0')
                    u1[b] = add(u1[b], mul(c1, cntD))
                    t1[b] = add(t1[b], mul(e1, cntD))
                    q1[b] = add(q1[b], add(mul(mul(w1, 10), cntD), mul(c1, sumD)))
                
                totEndC = add(e1, w1)
                if c == '+' or c == '?':
                    u0[b] = add(u0[b], c1)
                    t0[b] = add(t0[b], totEndC)
                if b > 0 and (c == ')' or c == '?'):
                    u2[b - 1] = add(u2[b - 1], c1)
                    t2[b - 1] = add(t2[b - 1], totEndC)
            
            if c2 > 0:
                if c == '+' or c == '?':
                    u0[b] = add(u0[b], c2)
                    t0[b] = add(t0[b], e2)
                if b > 0 and (c == ')' or c == '?'):
                    u2[b - 1] = add(u2[b - 1], c2)
                    t2[b - 1] = add(t2[b - 1], e2)
        
        v0, u0 = u0, v0
        s0, t0 = t0, s0
        v1, u1 = u1, v1
        s1, t1 = t1, s1
        p1, q1 = q1, p1
        v2, u2 = u2, v2
        s2, t2 = t2, s2
    
    final2 = [0] * (n + 2)
    finalS = [0] * (n + 2)
    for b in range(n + 1):
        final2[b] = add(final2[b], v2[b])
        finalS[b] = add(finalS[b], s2[b])
        if v1[b] > 0:
            final2[b] = add(final2[b], v1[b])
            finalS[b] = add(finalS[b], add(s1[b], p1[b]))
    
    ans = finalS[0]
    print(ans)

solve()

Ruby solution:
MOD = 998244353

def add(a, b)
  (a + b) % MOD
end

def mul(a, b)
  (a * b) % MOD
end

s = gets.chomp
n = s.size

v0 = Array.new(n + 2, 0)
s0 = Array.new(n + 2, 0)
v1 = Array.new(n + 2, 0)
s1 = Array.new(n + 2, 0)
p1 = Array.new(n + 2, 0)
v2 = Array.new(n + 2, 0)
s2 = Array.new(n + 2, 0)

v0[0] = 1

n.times do |i|
  u0 = Array.new(n + 2, 0)
  t0 = Array.new(n + 2, 0)
  u1 = Array.new(n + 2, 0)
  t1 = Array.new(n + 2, 0)
  q1 = Array.new(n + 2, 0)
  u2 = Array.new(n + 2, 0)
  t2 = Array.new(n + 2, 0)

  c = s[i]
  (0..n).each do |b|
    c0 = v0[b]
    e0 = s0[b]
    c1 = v1[b]
    e1 = s1[b]
    w1 = p1[b]
    c2 = v2[b]
    e2 = s2[b]

    if c == '(' || c == '?'
      if b + 1 <= n
        u0[b + 1] = add(u0[b + 1], c0)
        t0[b + 1] = add(t0[b + 1], e0)
      end
    end

    if c == '?' || c =~ /[0-9]/
      ok0 = (c == '?' || c == '0')
      if ok0
        u2[b] = add(u2[b], c0)
        t2[b] = add(t2[b], e0)
      end

      cnt9 = 0
      sum9 = 0
      if c == '?'
        cnt9 = 9
        sum9 = 45
      elsif c >= '1' && c <= '9'
        cnt9 = 1
        sum9 = c.ord - '0'.ord
      end
      if cnt9 > 0
        u1[b] = add(u1[b], mul(c0, cnt9))
        t1[b] = add(t1[b], mul(e0, cnt9))
        q1[b] = add(q1[b], mul(c0, sum9))
      end
    end

    if c1 > 0
      if c == '?' || c =~ /[0-9]/
        cntD = 0
        sumD = 0
        if c == '?'
          cntD = 10
          sumD = 45
        else
          cntD = 1
          sumD = c.ord - '0'.ord
        end
        u1[b] = add(u1[b], mul(c1, cntD))
        t1[b] = add(t1[b], mul(e1, cntD))
        q1[b] = add(q1[b], add(mul(mul(w1, 10), cntD), mul(c1, sumD)))
      end

      totEndC = add(e1, w1)
      if c == '+' || c == '?'
        u0[b] = add(u0[b], c1)
        t0[b] = add(t0[b], totEndC)
      end
      if b > 0 && (c == ')' || c == '?')
        u2[b - 1] = add(u2[b - 1], c1)
        t2[b - 1] = add(t2[b - 1], totEndC)
      end
    end

    if c2 > 0
      if c == '+' || c == '?'
        u0[b] = add(u0[b], c2)
        t0[b] = add(t0[b], e2)
      end
      if b > 0 && (c == ')' || c == '?')
        u2[b - 1] = add(u2[b - 1], c2)
        t2[b - 1] = add(t2[b - 1], e2)
      end
    end
  end

  v0 = u0
  s0 = t0
  v1 = u1
  s1 = t1
  p1 = q1
  v2 = u2
  s2 = t2
end

final2 = Array.new(n + 2, 0)
finalS = Array.new(n + 2, 0)

(0..n).each do |b|
  final2[b] = add(final2[b], v2[b])
  finalS[b] = add(finalS[b], s2[b])
  if v1[b] > 0
    final2[b] = add(final2[b], v1[b])
    finalS[b] = add(finalS[b], add(s1[b], p1[b]))
  end
end

ans = finalS[0]
puts ans