Untitled

///Dux
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define reset(a) memset(a, 0, sizeof(a))
#define For(i,a,b)    for(int i=a; i<=b; i++)
#define Fod(i,a,b)    for(int i=a; i>=b; i--)
#define vii vector<int, int>
#define vll vector<ll, ll>
#define NMAX 1003
#define MOD (ll)(111539786)
#define oo (ll)111000111000111000
#define TIME cout << "\nTime: " << clock()/(double) 1000 << "s "
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
#define dux "SPELL"
#define inp freopen(dux".inp", "r", stdin);
#define out freopen(dux".out", "w", stdout);
#define MN int main()

using namespace std;

int t;
string str;
pair<char, ll> a[NMAX];
ll f[NMAX], s[NMAX];

MN
{
    fast;
    cin >> t;
    while(t--)
    {
        cin >> str;
        int n = str.length();
        ll num = 0, cnt = 0;
        For(i,0, n-1)
        {
            if(str[i] >= 'a' && str[i] <= 'z')
            {
                a[cnt].se = num % MOD;
                a[++cnt].fi = str[i];
                num = 0;
            }
            else
            {
                num = num * 10 + str[i] - '0';
            }
        }
        a[cnt].se = num % MOD;
        int last[350];
        memset(last, 0, sizeof last);
        memset(f, 0, sizeof f);
        memset(s, 0, sizeof s);
        f[0] = s[0] = 1;
        For(i, 1, cnt)
        {
            if(last[a[i].fi] != 0)
            {
                f[i] = (((f[i] + s[i-1]) % MOD) - s[last[a[i].fi]] + MOD * MOD) % MOD;
                f[i] = (f[i] + f[last[a[i].fi]]) % MOD;
            }
            else
            {
                f[i] = (f[i] + s[i-1]) % MOD;
            }
            last[a[i].fi] = i;
            s[i] = (s[i-1] + (f[i] * a[i].se) % MOD) % MOD;
//            assert(f[i] >= 0);
            assert(s[i] >= 0);
        }
        cout << (s[cnt] - s[0] + MOD) % MOD << "\n";
    }
}