Let us consider the case where the \(\displaystyle \frac{|T|}2\)-th character of a 1122-string \(T\) is fixed at the \(i\)-th character of \(S\). (Let us call this problem the subproblem.) The answer to the original problem is the sum of this value over \(i=1,2,\ldots,|S|\).

Let \(p\) be the number occurrences of the digit \(S_i\) to the right of the \(i\)-th character, and \(q\) be the number of occurrences of the digit \((S_i+1)\) to the right of \(i\). These values \(p\) and \(q\) can be computed fast enough using cumulative sums. We claim that the sought answer to the subproblem can be represented as \(\displaystyle \binom{p+q}{p+1}\).

Proof \(1\):

When the length of 1122-strings is fixed to \(2k\), we need to pick \((k-1)\) characters out of the \(p\) characters, and \(k\) characters from the \(q\) characters (Note that the \(\displaystyle \left( \frac{|T|}2 \right)\)-th character is fixed.) So the answer to the subproblem is

\[\begin{aligned} &\phantom{=} \sum_{k\geq 1} \binom{p}{k-1}\binom{q}k\\ &= \sum_{k\geq 1} \binom{p}{k-1}\binom{q}{q-k}\\ &=\sum_{k_1+k_2=q-1}\binom{p}{k_1}\binom{q}{k_2}\\ &=\left[x^{q-1}\right]\left(\sum_{k_1\geq 0}\binom{p}{k_1}x^{k_1}\right)\left(\sum_{k_2\geq 0}\binom{q}{k_2}x^{k_2}\right)\\ &=\left[x^{q-1}\right] (1+x)^{p+q}\\ &=\binom{p+q}{q-1}=\binom{p+q}{p+1}. \end{aligned}\]

Proof \(2\):

Let \(X\) and \(Y\) be the indices counted for \(p\) and \(q\), respectively. (We ha \(|X|=p\) and \(|Y|=q\). Pick exactly \((p+1)\) elements from \(X \cup Y\). Let \(T'\) be the string obtained by concatenating the characters at the unchosen indices in \(X\), the chosen indices in \(X\), and \(i\). Then, \(T'\) is a 1122-string, and the ways of picking \(p+1\) elements and the 1122-strings correspond one-to-one. Therefore, the answer to the subproblem is \(\displaystyle \binom{p+q}{p+1}\).

Hence, the problem can be solved by finding \(p\) and \(q\) defined above, and compute the sum of \(\displaystyle \binom{p+q}{p+1}\). The cumulative sums and binomial coefficients can be precalculated in \(O(|S|)\) time, so the problem can be solved in a total of \(O(|S|)\) time, too.

The problem can be solved by appropriately implementing this algorithm.

Sample code (Python3)

MOD = 998244353
INF = 2_000_000 + 2025

fact = [0] * (INF + 1)
finv = [0] * (INF + 1)
fact[0] = 1
for i in range(1, INF + 1):
    fact[i] = fact[i - 1] * i % MOD
finv[INF] = pow(fact[INF], MOD - 2, MOD)
for i in range(INF, 0, -1):
    finv[i - 1] = finv[i] * i % MOD

def comb(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fact[n] * finv[k] % MOD * finv[n - k] % MOD

s = [ord(c) - ord('0') for c in input()]
n = len(s)
d = [[0] * (n + 1) for _ in range(10)]
for i in range(n):
    for j in range(10):
        d[j][i + 1] = d[j][i]
    d[s[i]][i + 1] += 1
ans = 0
for i in range(n - 1):
    if s[i] == 9:
        continue
    p = d[s[i]][i + 1] - 1
    q = d[s[i] + 1][n] - d[s[i] + 1][i + 1]
    ans = (ans + comb(p + q, p + 1)) % MOD
print(ans)