If \(|S|=1\), we may directly output the input.
Hereinafter we will assume otherwise.

For simplicity, we will rephrase the problem as follows.

We construct \(T\) from all possible set \(A\) uniformly at random. Find the expected value of evaluation of \(T\), multiplied by \(2^{|S|-1}\).

Here, instead of considering “the sum of evaluations of some number of expressions”, we will consider “how much each digit of \(S\) contributes to the final answer.” (Such technique of considering summations the other way round is sometimes called “contribution to the sum” technique.)
Now, let us focus on the \(k\)-th digit from the end.

• The digit will placed in the \(1\)’s place with the probability of \(\frac{1}{2}\)
• The digit will placed in the \(10\)’s place with the probability of \(\frac{1}{4}\)
• The digit will placed in the \(100\)’s place with the probability of \(\frac{1}{8}\)
• \(\dots\)
• The digit will placed in the \(10^{k-2}\)’s place with the probability of \(\frac{1}{2^{k-1}}\)
• The digit will placed in the \(10^{k-1}\)’s place with the probability of \(\frac{1}{2^{k-1}}\)

Note the exception in the last item.

Let \(x\) be the \(k\)-th digit of \(S\), counted from the right; then this digit increases the final answer by \(x \times (1 \times \frac{1}{2}+10 \times \frac{1}{4} + 100 \times \frac{1}{8} + \dots + 10^{k-2} \times \frac{1}{2^{k-1}} + 10^{k-1} \times \frac{1}{2^{k-1}})\). This is a sum of a geometric progression with an exceptional final term, multiplied by \(x\). We may either compute this value by the formula of sum of geometric progression, or in a cumulative-sum-like way from the least significant digit to the most.

The total complexity is \(O(N)\), which is fast enough to solve this problem.

Sample code (C++)

#include<bits/stdc++.h>
#define mod 998244353

using namespace std;

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

int main(){
  string s;
  cin >> s;
  if(s.size()==1){cout << s << '\n';return 0;}
  long long res=0,del=1,cur=0;
  for(int i=s.size()-1;i>=0;i--){
    cur+=del;cur%=mod;
    long long ce=(cur+del)%mod;
    res+=(s[i]-'0')*ce;res%=mod;
    del*=5;del%=mod;
  }
  res*=power(2,s.size()-2);res%=mod;
  cout << res << '\n';
  return 0;
}

Bonus! Construct a case for which the output is \(0\).