Search for 404

#include <bits/stdc++.h>

using namespace std;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)
#define ff     first
#define ss     second
#define pb     push_back

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    _test
    {
        int n;
        cin>>n;

        string s;
        cin>>s;

        int MOD = 1e9 + 7;

        int c = count(s.begin(), s.end(), '*');
        ll int pow = 1;
        for(int i=1; i<c; i++)
            (pow *= 2) %= MOD;

        ll int cnt4 = 0;
        ll int cnt40 = 0;

        ll int ans = 0;

        for(auto e: s)
        {
            if(e == '4')
            {
                (ans += cnt40) %= MOD;
                cnt4++;
            }
            else if(e == '0')
                (cnt40 += cnt4) %= MOD;
        }

        if(c>=1)
        (ans *= (pow*2)%MOD) %= MOD;

        {
            int c4 = count(s.begin(), s.end(), '4');
            int c4s = 0;

            for(auto e: s)
            {
                c4 -= (e == '4');

                if(e == '*')
                {
                    ll int x = c4 * 1ll * c4s;
                    x %= MOD;

                    x *= pow;
                    x %= MOD;

                    (ans += x) %= MOD;
                }

                c4s += (e == '4');
            }
        }

        {
            int c4=0;
            int c40 =0;

            for(auto e: s)
            {
                c4 += (e == '4');

                if(e == '0')
                    (c40 += c4) %= MOD;

                if(e == '*')
                {
                    ll int x = c40;
                    x %= MOD;

                    x *= pow;
                    x %= MOD;

                    (ans += x) %= MOD;
                }
            }
        }

        {
            reverse(s.begin(), s.end());
            int c4=0;
            int c40 =0 ;

            for(auto e: s)
            {
                c4 += (e == '4');

                if(e == '0')
                    (c40 += c4) %= MOD;

                if(e == '*')
                {
                    ll int x = c40;
                    x %= MOD;

                    x *= pow;
                    x %= MOD;

                    (ans += x) %= MOD;
                }
            }
            reverse(s.begin(), s.end());
        }

        pow = 1;
        for(int i=1; i<=c-2; i++)  (pow *= 2) %= MOD;
        if(c == 1)  pow = 0;

        {
            int cs = count(s.begin(), s.end(), '*');
            int css = 0;

            for(auto e: s)
            {
                cs -= (e == '*');

                if(e == '0')
                {
                    ll int x = cs * 1ll * css;
                    x %= MOD;

                    x *= pow;
                    x %= MOD;

                    (ans += x) %= MOD;
                }

                css += (e == '*');
            }
        }

        {
            int cs = 0 ;

            for(auto e: s)
            {
                cs += (e == '*');

                if(e == '4')
                {
                    ll int x = ((cs*(cs-1))/2);
                    x %= MOD;

                    x *= pow;
                    x %= MOD;

                    (ans += x) %= MOD;
                }
            }
        }

        {
            reverse(s.begin(), s.end());
            int cs = 0 ;

            for(auto e: s)
            {
                cs += (e == '*');

                if(e == '4')
                {
                    ll int x = ((cs*(cs-1))/2);
                    x %= MOD;

                    x *= pow;
                    x %= MOD;

                    (ans += x) %= MOD;
                }
            }
            reverse(s.begin(), s.end());
        }

        pow = 1;
        for(int i=1; i<=c-3; i++)  (pow *= 2) %= MOD;
        ll int cs = count(s.begin(), s.end(), '*');
        ll int x = cs*(cs-1ll);
        x *= (cs-2ll);
        x /= 6;
        x %= MOD;
        x *= pow;
        x %= MOD;
        (ans += x) %= MOD;

        cout<<ans<<"\n";
    }
}