Ideone.com

fork download

copy

 
 
#include <bits/stdc++.h>
using namespace std;
 
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
 
#define Boost           ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define see(x)        cerr<< __LINE__ << ": " << (#x) << " is "<< (x) <<'\n';
#define pb              push_back
#define inf             1e10
#define rep(i,n)        for(int i=0;i<n;i++)
#define rep1(i,n)       for(int i=1;i<=n;i++)
#define ll              long long
#define MOD             1000000007
#define mem(x,i)        memset(x,i,sizeof x)
#define Ones(x)         __builtin_popcount(x);
#define PI              acos(-1.0)
#define ff              first
#define ss              second
#define T               int t;cin>>t;while(t--)
#define ok              cout<<"ok"<<endl;
#define all(x)          (x).begin(),(x).end()
#define ordered_set     tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define nln	            cout<<endl;
#define maxn 300005
 
int dx[]= {-1,0,1,0}; //up,right,down,left
int dy[]= {0,1,0,-1};
 
 
ll cal(ll r,ll n)
{
    r=r-1;
    n=n+r;
//    see(n)
//    see(r)
    ll i,j,res=1;
    if(r>n-r)
        r=n-r;
    for(i=0; i<r; i++)
    {
        res*=((n-i))%MOD;
        res/=((i+1))%MOD;
 
    }
    return res%MOD;
}
 
int main()
{
    Boost;
 
    T
    {
        ll n,x=0,i,j,prev=0,digit,ans=1,flag=0;
        string s;
        cin>>n;
        cin>>s;
 
        for(i=0; i<s.size(); i++)
        {
            if(s[i]!='-')
            {
                if(prev==0)
                {
                    prev=s[i]-'0';
                }
                else
                {
                    x=s[i]-'0';
                    if(x<prev)
                    {
                        flag=1;
                        break;
                    }
                    else
                        prev=x;
                }
            }
        }
        if(flag)
        {
            cout<<"0"<<endl;
            continue;
        }
 
        prev=0;
        x=0;
        for(i=0; i<s.size(); i++)
        {
            if(s[i]!='-')
            {
                if(x>0)
                {
                    //see(x)
                    if(prev==0)
                    {
                        prev=s[i]-'0';
                        digit=prev;
                        //see(digit)
                        ans*=(cal(digit,x))%MOD;
                        x=0;
                    }
                    else
                    {
                        digit=(s[i]-'0')-prev-1+2;
                        //see(digit)
                        ans*=(cal(digit,x))%MOD;
                        x=0;
                        prev=s[i]-'0';
                    }
                }
                else
                {
                    prev=s[i]-'0';
                }
            }
            else
                x++;
        }
        //see(ans)
        //see(x)
        if(x>0)
        {
            if(prev==0)
            {
                ans*=(cal(9,x))%MOD;
            }
            else
            {
                //see(prev)
                ll f=9-prev+1;
                // see(f)
                ans*=(cal(f,x))%MOD;
            }
        }
        cout<<ans<<endl;
    }
 
 
 
}
/*
1
5
--3--
 
*/

CgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vI2luY2x1ZGUgPGV4dC9wYl9kcy9hc3NvY19jb250YWluZXIuaHBwPgovLyNpbmNsdWRlIDxleHQvcGJfZHMvdHJlZV9wb2xpY3kuaHBwPgovL3VzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwoKI2RlZmluZSBCb29zdCAgICAgICAgICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTtjaW4udGllKDApLGNvdXQudGllKDApCiNkZWZpbmUgc2VlKHgpICAgICAgICBjZXJyPDwgX19MSU5FX18gPDwgIjogIiA8PCAoI3gpIDw8ICIgaXMgIjw8ICh4KSA8PCdcbic7CiNkZWZpbmUgcGIgICAgICAgICAgICAgIHB1c2hfYmFjawojZGVmaW5lIGluZiAgICAgICAgICAgICAxZTEwCiNkZWZpbmUgcmVwKGksbikgICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiNkZWZpbmUgcmVwMShpLG4pICAgICAgIGZvcihpbnQgaT0xO2k8PW47aSsrKQojZGVmaW5lIGxsICAgICAgICAgICAgICBsb25nIGxvbmcKI2RlZmluZSBNT0QgICAgICAgICAgICAgMTAwMDAwMDAwNwojZGVmaW5lIG1lbSh4LGkpICAgICAgICBtZW1zZXQoeCxpLHNpemVvZiB4KQojZGVmaW5lIE9uZXMoeCkgICAgICAgICBfX2J1aWx0aW5fcG9wY291bnQoeCk7CiNkZWZpbmUgUEkgICAgICAgICAgICAgIGFjb3MoLTEuMCkKI2RlZmluZSBmZiAgICAgICAgICAgICAgZmlyc3QKI2RlZmluZSBzcyAgICAgICAgICAgICAgc2Vjb25kCiNkZWZpbmUgVCAgICAgICAgICAgICAgIGludCB0O2Npbj4+dDt3aGlsZSh0LS0pCiNkZWZpbmUgb2sgICAgICAgICAgICAgIGNvdXQ8PCJvayI8PGVuZGw7CiNkZWZpbmUgYWxsKHgpICAgICAgICAgICh4KS5iZWdpbigpLCh4KS5lbmQoKQojZGVmaW5lIG9yZGVyZWRfc2V0ICAgICB0cmVlPGludCwgbnVsbF90eXBlLGxlc3M8aW50PiwgcmJfdHJlZV90YWcsdHJlZV9vcmRlcl9zdGF0aXN0aWNzX25vZGVfdXBkYXRlPgojZGVmaW5lIG5sbgkgICAgICAgICAgICBjb3V0PDxlbmRsOwojZGVmaW5lIG1heG4gMzAwMDA1CgppbnQgZHhbXT0gey0xLDAsMSwwfTsgLy91cCxyaWdodCxkb3duLGxlZnQKaW50IGR5W109IHswLDEsMCwtMX07CgoKbGwgY2FsKGxsIHIsbGwgbikKewogICAgcj1yLTE7CiAgICBuPW4rcjsKLy8gICAgc2VlKG4pCi8vICAgIHNlZShyKQogICAgbGwgaSxqLHJlcz0xOwogICAgaWYocj5uLXIpCiAgICAgICAgcj1uLXI7CiAgICBmb3IoaT0wOyBpPHI7IGkrKykKICAgIHsKICAgICAgICByZXMqPSgobi1pKSklTU9EOwogICAgICAgIHJlcy89KChpKzEpKSVNT0Q7CgogICAgfQogICAgcmV0dXJuIHJlcyVNT0Q7Cn0KCmludCBtYWluKCkKewogICAgQm9vc3Q7CgogICAgVAogICAgewogICAgICAgIGxsIG4seD0wLGksaixwcmV2PTAsZGlnaXQsYW5zPTEsZmxhZz0wOwogICAgICAgIHN0cmluZyBzOwogICAgICAgIGNpbj4+bjsKICAgICAgICBjaW4+PnM7CgogICAgICAgIGZvcihpPTA7IGk8cy5zaXplKCk7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGlmKHNbaV0hPSctJykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYocHJldj09MCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBwcmV2PXNbaV0tJzAnOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHg9c1tpXS0nMCc7CiAgICAgICAgICAgICAgICAgICAgaWYoeDxwcmV2KQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgZmxhZz0xOwogICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICBwcmV2PXg7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgaWYoZmxhZykKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQ8PCIwIjw8ZW5kbDsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQoKICAgICAgICBwcmV2PTA7CiAgICAgICAgeD0wOwogICAgICAgIGZvcihpPTA7IGk8cy5zaXplKCk7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGlmKHNbaV0hPSctJykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYoeD4wKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIC8vc2VlKHgpCiAgICAgICAgICAgICAgICAgICAgaWYocHJldj09MCkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHByZXY9c1tpXS0nMCc7CiAgICAgICAgICAgICAgICAgICAgICAgIGRpZ2l0PXByZXY7CiAgICAgICAgICAgICAgICAgICAgICAgIC8vc2VlKGRpZ2l0KQogICAgICAgICAgICAgICAgICAgICAgICBhbnMqPShjYWwoZGlnaXQseCkpJU1PRDsKICAgICAgICAgICAgICAgICAgICAgICAgeD0wOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBkaWdpdD0oc1tpXS0nMCcpLXByZXYtMSsyOwogICAgICAgICAgICAgICAgICAgICAgICAvL3NlZShkaWdpdCkKICAgICAgICAgICAgICAgICAgICAgICAgYW5zKj0oY2FsKGRpZ2l0LHgpKSVNT0Q7CiAgICAgICAgICAgICAgICAgICAgICAgIHg9MDsKICAgICAgICAgICAgICAgICAgICAgICAgcHJldj1zW2ldLScwJzsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcHJldj1zW2ldLScwJzsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB4Kys7CiAgICAgICAgfQogICAgICAgIC8vc2VlKGFucykKICAgICAgICAvL3NlZSh4KQogICAgICAgIGlmKHg+MCkKICAgICAgICB7CiAgICAgICAgICAgIGlmKHByZXY9PTApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGFucyo9KGNhbCg5LHgpKSVNT0Q7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvL3NlZShwcmV2KQogICAgICAgICAgICAgICAgbGwgZj05LXByZXYrMTsKICAgICAgICAgICAgICAgIC8vIHNlZShmKQogICAgICAgICAgICAgICAgYW5zKj0oY2FsKGYseCkpJU1PRDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBjb3V0PDxhbnM8PGVuZGw7CiAgICB9CgoKCn0KLyoKMQo1Ci0tMy0tCgoqLwo=

Success #stdin #stdout 0.06s 4672KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/k5OTdF

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language