QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217515#6325. Peaceful ResultsCharlieVinnieAC ✓376ms117040kbC++1710.7kb2023-10-16 22:19:182023-10-16 22:19:18

Judging History

你现在查看的是最新测评结果

  • [2023-10-16 22:19:18]
  • 评测
  • 测评结果:AC
  • 用时:376ms
  • 内存:117040kb
  • [2023-10-16 22:19:18]
  • 提交

answer

#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
#define range basic_string_view
using namespace std; typedef long long ll;
namespace Math::ZPoly
{

using LL=long long;
constexpr int MOD=998244353,G=114514,MAXN=1<<22;
int qpow(LL a,LL b) { LL r=1;for(;b;(b&1)?r=r*a%MOD:0,a=a*a%MOD,b>>=1);return r; }
int madd(int x) { return x; }
int mmul(int x) { return x; }
int msub(int x,int y) { return (x-=y)<0?x+=MOD:x; }
int mdiv(int x,int y) { return (LL)x*qpow(y,MOD-2)%MOD; }
template<typename ...Args>int madd(int x,Args ...y) { return (x+=madd(y...))>=MOD?x-=MOD:x; }
template<typename ...Args>int mmul(int x,Args ...y) { return (LL)x*mmul(y...)%MOD; }

class PolyTemp
{
 private:
    static PolyTemp V;
    int g[MAXN+5],c1[MAXN+5],c2[MAXN+5];
    PolyTemp()
    {
        int nn=1<<(__lg(MAXN-1)+1);
        for(int i=2;i<=nn;i<<=1)
        {
            g[i>>1]=1;
            int gn=qpow(G,(MOD-1)/i);
            for(int j=(i>>1)+1;j<i;j++) g[j]=mmul(g[j-1],gn);
        }
    }
    friend class Polynomial;
}PolyTemp::V{};

// A class for polynomials in F_{MOD}.
class Polynomial: public vector<int>
{
 private:
    static constexpr int NTT_LIM=100;
    static constexpr auto &g=PolyTemp::V.g,&c1=PolyTemp::V.c1,&c2=PolyTemp::V.c2;
    using BaseT=vector<int>;
#define NTT_CHECK(n,m) (n+m<=NTT_LIM || 1ll*n*m<5ll*(n+m)*__lg(n+m))
#define EXTEND(n) (1<<(__lg((n)-1)+1))
#define MCPY(a,b,s) memcpy(a,b,(s)*sizeof(int))
#define MSET(a,b,s) memset(a,b,(s)*sizeof(int))
 public:
    static void DIT(int *a,int len)
    {
        for(int i=len>>1;i;i>>=1)
            for(int j=0;j<len;j+=i<<1)
                for(int k=0,x,y;k<i;k++)
                    x=a[j+k],y=a[i+j+k],a[j+k]=madd(x,y),a[i+j+k]=mmul(g[i+k],msub(x,y));
    }
    static void DIF(int *a,int len)
    {
        for(int i=1;i<len;i<<=1)
            for(int j=0;j<len;j+=i<<1)
                for(int k=0,x,y;k<i;k++)
                    x=a[j+k],y=mmul(g[i+k],a[i+j+k]),a[j+k]=madd(x,y),a[i+j+k]=msub(x,y);
        int x=qpow(len,MOD-2);
        for(int i=0;i<len;i++) a[i]=mmul(a[i],x);
        reverse(a+1,a+len);
    }
 private:
    static void __polyinv(const int *a,int *b,int len)
    {
        if(len==1) return b[0]=qpow(a[0],MOD-2),void();
        __polyinv(a,b,(len+1)>>1);
        int nn=EXTEND(len<<1);
        MCPY(c1,a,len);
        MSET(b+len,0,nn-len);
        MSET(c1+len,0,nn-len);
        DIT(b,nn),DIT(c1,nn);
        for(int i=0;i<nn;i++) b[i]=mmul(b[i],msub(2,mmul(b[i],c1[i])));
        DIF(b,nn),MSET(b+len,0,nn-len);
    }
    static void __polyln(const int *a,int *b,int len)
    {
        __polyinv(a,b,len);
        for(int i=1;i<len;i++) c1[i-1]=mmul(i,a[i]);
        int nn=EXTEND(len<<1);
        MSET(b+len,0,nn-len);
        MSET(c1+len,0,nn-len);
        DIT(b,nn),DIT(c1,nn);
        for(int i=0;i<nn;i++) b[i]=mmul(b[i],c1[i]);
        DIF(b,nn),MSET(b+len,0,nn-len);
        for(int i=len-1;i>0;i--) b[i]=mdiv(b[i-1],i);
        b[0]=0;
    }
    static void __polyexp(const int *a,int *b,int l,int r)
    {
        if(l==r-1) return b[l]=(l?mdiv(b[l],l):1),void();
        int len=r-l,mid=(l+r)>>1;
        __polyexp(a,b,l,mid);
        for(int i=0;i<len;i++) c1[i]=a[i];
        MCPY(c2,b+l,mid-l);
        MSET(c2+mid-l,0,r-mid);
        if(NTT_CHECK(len,len)) for(int i=len-1;i>=0;i--)
        {
            int tmp=0;
            for(int j=0;j<=i;j++)
                tmp=madd(tmp,mmul(c1[j],c2[i-j]));
            c1[i]=tmp;
        }
        else
        {
            DIT(c1,len),DIT(c2,len);
            for(int i=0;i<len;i++) c1[i]=mmul(c1[i],c2[i]);
            DIF(c1,len);
        }
        for(int i=mid;i<r;i++) b[i]=madd(b[i],c1[i-l]);
        __polyexp(a,b,mid,r);
    }
 public:
    using BaseT::BaseT;
    using BaseT::operator=;
    int operator ()(int x)const
    {
        int res=0,sz=size();
        for(int i=sz-1;i>=0;i--)
            res=madd(mmul(res,x),(*this)[i]);
        return res;
    }
#define DEF_OP(op) \
    Polynomial operator op(const Polynomial &p)const \
    { return Polynomial(*this)op##=p; } \
    Polynomial &operator op##=(const Polynomial &p)
    DEF_OP(+)
    {
        int n=size(),m=p.size();
        if(n<m) resize(m);
        for(int i=0;i<m;i++)
            (*this)[i]=madd((*this)[i],p[i]);
        return *this;
    }
    DEF_OP(-)
    {
        int n=size(),m=p.size();
        if(n<m) resize(m);
        for(int i=0;i<m;i++)
            (*this)[i]=msub((*this)[i],p[i]);
        return *this;
    }
    DEF_OP(*)
    {
        int n=size(),m=p.size(),sz=n+m-1;
        if(!n || !m) return clear(),*this;
        resize(sz);
        if(NTT_CHECK(n,m))
        {
            MCPY(c1,data(),n);
            MSET(c2,0,sz);
            for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                    c2[i+j]=madd(c2[i+j],mmul(c1[i],p[j]));
            MCPY(data(),c2,sz);
        }
        else if(this==addressof(p))
        {
            int nn=EXTEND(sz);
            MCPY(c1,data(),n);
            MSET(c1+n,0,nn-n);
            DIT(c1,nn);
            for(int i=0;i<nn;i++) c1[i]=mmul(c1[i],c1[i]);
            DIF(c1,nn);
            MCPY(data(),c1,sz);
        }
        else
        {
            int nn=EXTEND(sz);
            MCPY(c1,data(),n),MCPY(c2,p.data(),m);
            MSET(c1+n,0,nn-n),MSET(c2+m,0,nn-m);
            DIT(c1,nn),DIT(c2,nn);
            for(int i=0;i<nn;i++) c1[i]=mmul(c1[i],c2[i]);
            DIF(c1,nn);
            MCPY(data(),c1,sz);
        }
        return *this;
    }
    DEF_OP(/) { return (*this)*=p.inv(); }
    DEF_OP(%) { return (*this)=divr(*this,p).second; }
#undef DEF_OP
    Polynomial &operator *=(int k)
    { for(auto &i: *this) i=mmul(i,k); return *this; }
    friend Polynomial operator *(const Polynomial &p,int k)
    { return Polynomial(p)*=k; }
    friend Polynomial operator *(int k,const Polynomial &p)
    { return Polynomial(p)*=k; }
    friend Polynomial derivative(const Polynomial &p)
    {
        int sz=p.size();
        Polynomial q(sz-1);
        for(int i=1;i<sz;i++) q[i-1]=mmul(p[i],i);
        return q;
    }
    friend Polynomial integral(const Polynomial &p)
    {
        int sz=p.size();
        Polynomial q(sz+1);
        for(int i=1;i<sz;i++) q[i+1]=mdiv(p[i],i+1);
        return q;
    }
    Polynomial inv()const
    {
        if(empty() || front()==0) throw runtime_error("[x^0]f(x)=0, f(x)^-1 doesn't exist.\n");
        int sz=size(),nn=1<<(__lg((sz<<1)-1)+1);
        Polynomial q(nn);
        __polyinv(data(),q.data(),sz);
        return q.resize(sz),q;
    }
    friend Polynomial ln(const Polynomial &p)
    {
        if(p.empty() || p[0]!=1) throw runtime_error("[x^0]f(x)!=1, ln(f(x)) doesn't exist.\n");
        int sz=p.size(),nn=1<<(__lg((sz<<1)-1)+1);
        Polynomial q(nn);
        __polyln(p.data(),q.data(),sz);
        return q.resize(sz),q;
    }
    friend Polynomial exp(const Polynomial &p)
    {
        if(p.empty()) return Polynomial{1};
        if(p[0]!=0) throw runtime_error("[x^0]f(x)!=0, exp(f(x)) doesn't exist.\n");
        static int c[MAXN];
        int sz=p.size(),nn=1<<(__lg(sz-1)+1);
        for(int i=0;i<sz;i++) c[i]=mmul(i,p[i]);
        Polynomial q(nn);
        __polyexp(c,q.data(),0,nn);
        return q.resize(sz),q;
    }
    friend pair<Polynomial,Polynomial> divr(const Polynomial &f,const Polynomial &g)
    {
        if(f.size()<g.size()) return make_pair(Polynomial{0},f);
        int n=f.size()-1,m=g.size()-1;
        Polynomial fr(n+1),gr(m+1);
        for(int i=0;i<=n;i++) fr[i]=f[n-i];
        for(int i=0;i<=m;i++) gr[i]=g[m-i];
        fr.resize(n-m+1),gr.resize(n-m+1),fr*=gr.inv();
        fr.resize(n-m+1),reverse(fr.begin(),fr.end());
        gr=f-fr*g,gr.resize(m);
        return make_pair(fr,gr);
    }
#undef NTT_CHECK
#undef EXTEND
#undef MCPY
#undef MSET
};

} // namespace ZPoly
constexpr int mod=998244353;
inline int qpow(int x,int y){int res=1;while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    int n,Ar,As,Ap,Br,Bs,Bp,Cr,Cs,Cp; cin>>n>>Ar>>As>>Ap>>Br>>Bs>>Bp>>Cr>>Cs>>Cp;
    // RRR SSS PPP RSP SPR PRS RPS PSR SRP
    ll co[9][10]={
        {1,0,0,1,0,0,1,0,0,Ar},
        {0,1,0,0,1,0,0,0,1,As},
        {0,0,1,0,0,1,0,1,0,Ap},
        {1,0,0,0,0,1,0,0,1,Br},
        {0,1,0,1,0,0,0,1,0,Bs},
        {0,0,1,0,1,0,1,0,0,Bp},
        {1,0,0,0,1,0,0,1,0,Cr},
        {0,1,0,0,0,1,1,0,0,Cs},
        {0,0,1,1,0,0,0,0,1,Cp}
    };
    ll _co[9][10]; memcpy(_co,co,sizeof(co));
    For(i,0,6){
        int mx=0,p=1e9;
        For(j,i,8){
            int t=1e9; For(k,0,8) if(co[j][k]) { t=k; break; }
            if(t<p) p=t,mx=j;
        }
        assert(p!=1e9);
        assert(co[mx][p]);
        if(mx!=i) swap(co[i],co[mx]);
        assert(co[i][p]);
        For(j,0,8) if(j!=i&&co[j][p]){
            ll r=co[j][p]; For(k,0,9) co[j][k]=co[j][k]*co[i][p]-r*co[i][k];
        }
        For(_,0,8) debug(co[_]);; debug('\n');
    }
    For(i,0,8) debug(co[i]);
    int a[9]={0};
    For(i,0,6){
        int p=0; while(!co[i][p]) p++;; if(co[i][9]%co[i][p]!=0) cout<<"0\n",exit(0);
        a[p]=co[i][9]/co[i][p];
    }
    debug(a);
    For(i,0,8){
        int t=0; For(j,0,8) t=(t+1ll*_co[i][j]*a[j])%mod;; debug(i,t,_co[i][9]); assert((t+mod)%mod==_co[i][9]);
    }
    vector<int> cp(n*2+1); cp[0]=1; For(i,1,n*2) cp[i]=1ll*cp[i-1]*i%mod;
    vector<int> ci(n*2+1); ci[n*2]=qpow(cp[n*2],mod-2); Rev(i,n*2-1,0) ci[i]=1ll*ci[i+1]*(i+1)%mod;
    Math::ZPoly::Polynomial f(n+1),g(n+1),h(n+1);
    int m0=min({a[0],a[1],a[2]}),m1=min({a[3],a[4],a[5]}),m2=min({a[6],a[7],a[8]});
    For(i,0,n) f[i]=1ll*ci[a[0]-m0+i]*ci[a[1]-m0+i]%mod*ci[a[2]-m0+i]%mod;
    For(i,0,n) g[i]=1ll*ci[a[3]-m1+i]*ci[a[4]-m1+i]%mod*ci[a[5]-m1+i]%mod;
    For(i,0,n) h[i]=1ll*ci[a[6]-m2+i]*ci[a[7]-m2+i]%mod*ci[a[8]-m2+i]%mod;
    // int ans=0; For(i,0,n) For(j,0,n) For(k,0,n) if(i+j+k==m0+m1+m2) ans=(ans+1ll*f[i]*g[j]%mod*h[k])%mod;
    // cout<<1ll*ans*cp[n]%mod<<'\n';
    auto F=f*g; int ans=0;
    For(i,0,m0+m1+m2) ans=(ans+1ll*F[i]*h[m0+m1+m2-i])%mod;
    cout<<1ll*ans*cp[n]%mod<<'\n';
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: October 16 Mon, 21 : 07 : 54

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 24072kb

input:

2
2 0 0
1 1 0
1 0 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 17ms
memory: 21556kb

input:

3
0 1 2
3 0 0
1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 91ms
memory: 45436kb

input:

333333
111111 111111 111111
111111 111111 111111
111111 111111 111111

output:

383902959

result:

ok 1 number(s): "383902959"

Test #4:

score: 0
Accepted
time: 362ms
memory: 117040kb

input:

1500000
500000 500000 500000
500000 500000 500000
500000 500000 500000

output:

355543262

result:

ok 1 number(s): "355543262"

Test #5:

score: 0
Accepted
time: 359ms
memory: 116796kb

input:

1499999
499999 499999 500001
499999 499999 500001
499999 499999 500001

output:

934301164

result:

ok 1 number(s): "934301164"

Test #6:

score: 0
Accepted
time: 374ms
memory: 116964kb

input:

1500000
1 0 1499999
1499999 1 0
0 1499999 1

output:

1500000

result:

ok 1 number(s): "1500000"

Test #7:

score: 0
Accepted
time: 361ms
memory: 116704kb

input:

1499999
0 749999 750000
750000 0 749999
749999 750000 0

output:

713966599

result:

ok 1 number(s): "713966599"

Test #8:

score: 0
Accepted
time: 21ms
memory: 22932kb

input:

1
1 0 0
0 0 1
0 1 0

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 21ms
memory: 22736kb

input:

1
0 1 0
0 1 0
0 1 0

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 16ms
memory: 20864kb

input:

1
0 0 1
1 0 0
1 0 0

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 370ms
memory: 116936kb

input:

1499999
500000 500000 499999
499999 499999 500001
499999 499999 500001

output:

617065435

result:

ok 1 number(s): "617065435"

Test #12:

score: 0
Accepted
time: 16ms
memory: 22396kb

input:

2
1 1 0
0 0 2
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #13:

score: 0
Accepted
time: 358ms
memory: 116748kb

input:

1500000
500000 500001 499999
499999 500000 500001
499999 500000 500001

output:

925862004

result:

ok 1 number(s): "925862004"

Test #14:

score: 0
Accepted
time: 181ms
memory: 66860kb

input:

629197
210878 201408 216911
145293 266423 217481
194751 220179 214267

output:

447295633

result:

ok 1 number(s): "447295633"

Test #15:

score: 0
Accepted
time: 179ms
memory: 63704kb

input:

579097
200209 204257 174631
149110 148890 281097
138034 263752 177311

output:

71830925

result:

ok 1 number(s): "71830925"

Test #16:

score: 0
Accepted
time: 100ms
memory: 46076kb

input:

354224
100316 63899 190009
69306 123829 161089
140523 76088 137613

output:

44852283

result:

ok 1 number(s): "44852283"

Test #17:

score: 0
Accepted
time: 363ms
memory: 105280kb

input:

1229851
383009 323934 522908
551226 311238 367387
547622 353128 329101

output:

39721313

result:

ok 1 number(s): "39721313"

Test #18:

score: 0
Accepted
time: 184ms
memory: 76008kb

input:

858452
195309 312080 351063
384805 51797 421850
200466 301164 356822

output:

506491992

result:

ok 1 number(s): "506491992"

Test #19:

score: 0
Accepted
time: 374ms
memory: 113588kb

input:

1424218
661653 323895 438670
467846 488045 468327
369769 343207 711242

output:

782021141

result:

ok 1 number(s): "782021141"

Test #20:

score: 0
Accepted
time: 352ms
memory: 98936kb

input:

1079733
333391 427895 318447
579853 153924 345956
406031 300755 372947

output:

111229812

result:

ok 1 number(s): "111229812"

Test #21:

score: 0
Accepted
time: 179ms
memory: 63180kb

input:

572270
168517 197624 206129
238722 154914 178634
192692 145891 233687

output:

93444378

result:

ok 1 number(s): "93444378"

Test #22:

score: 0
Accepted
time: 102ms
memory: 50180kb

input:

470911
95201 196020 179690
143795 173744 153372
142604 154489 173818

output:

629148200

result:

ok 1 number(s): "629148200"

Test #23:

score: 0
Accepted
time: 128ms
memory: 52556kb

input:

514907
142312 117185 255410
52426 249434 213047
180346 59381 275180

output:

497502651

result:

ok 1 number(s): "497502651"

Test #24:

score: 0
Accepted
time: 123ms
memory: 47896kb

input:

406588
151239 177967 77382
93189 144948 168451
94378 135309 176901

output:

790871601

result:

ok 1 number(s): "790871601"

Test #25:

score: 0
Accepted
time: 55ms
memory: 33728kb

input:

175290
55982 60345 58963
48359 77923 49008
23679 74616 76995

output:

123245869

result:

ok 1 number(s): "123245869"

Test #26:

score: 0
Accepted
time: 367ms
memory: 112168kb

input:

1387914
512757 474809 400348
378268 216654 792992
649332 374567 364015

output:

676034326

result:

ok 1 number(s): "676034326"

Test #27:

score: 0
Accepted
time: 173ms
memory: 71128kb

input:

764222
219470 230830 313922
331893 97293 335036
97220 292440 374562

output:

158682546

result:

ok 1 number(s): "158682546"

Test #28:

score: 0
Accepted
time: 188ms
memory: 71052kb

input:

753135
242199 294626 216310
175239 287120 290776
282985 150249 319901

output:

971077263

result:

ok 1 number(s): "971077263"

Test #29:

score: 0
Accepted
time: 189ms
memory: 78244kb

input:

907648
254368 314623 338657
266634 210330 430684
203259 377229 327160

output:

657924076

result:

ok 1 number(s): "657924076"

Test #30:

score: 0
Accepted
time: 184ms
memory: 70292kb

input:

734407
287960 273092 173355
91803 383817 258787
317856 268839 147712

output:

302163640

result:

ok 1 number(s): "302163640"

Test #31:

score: 0
Accepted
time: 183ms
memory: 73524kb

input:

802408
296016 284435 221957
207041 242882 352485
117792 274366 410250

output:

54247530

result:

ok 1 number(s): "54247530"

Test #32:

score: 0
Accepted
time: 179ms
memory: 62420kb

input:

562487
158889 225035 178563
148413 302399 111675
148133 215119 199235

output:

169658542

result:

ok 1 number(s): "169658542"

Test #33:

score: 0
Accepted
time: 206ms
memory: 82848kb

input:

999120
389537 311486 298097
316708 332443 349969
261915 402318 334887

output:

352258886

result:

ok 1 number(s): "352258886"

Test #34:

score: 0
Accepted
time: 376ms
memory: 112944kb

input:

1409159
427245 484076 497838
435890 528804 444465
588832 314386 505941

output:

887383005

result:

ok 1 number(s): "887383005"

Test #35:

score: 0
Accepted
time: 194ms
memory: 83068kb

input:

1003619
340241 274051 389327
166457 383901 453261
211841 434615 357163

output:

353962733

result:

ok 1 number(s): "353962733"

Test #36:

score: 0
Accepted
time: 22ms
memory: 26984kb

input:

22574
9246 5094 8234
9209 7482 5883
12089 6331 4154

output:

60839910

result:

ok 1 number(s): "60839910"

Test #37:

score: 0
Accepted
time: 367ms
memory: 113300kb

input:

1415532
478588 564750 372194
512789 526677 376066
217017 566262 632253

output:

625939628

result:

ok 1 number(s): "625939628"

Test #38:

score: 0
Accepted
time: 186ms
memory: 68228kb

input:

662723
241713 270544 150466
205318 236372 221033
329239 165257 168227

output:

186211005

result:

ok 1 number(s): "186211005"

Test #39:

score: 0
Accepted
time: 362ms
memory: 99780kb

input:

1096822
586933 218335 291554
392825 346250 357747
326051 392267 378504

output:

128569855

result:

ok 1 number(s): "128569855"

Test #40:

score: 0
Accepted
time: 359ms
memory: 106020kb

input:

1246485
277064 449274 520147
467862 333900 444723
590215 427647 228623

output:

695555486

result:

ok 1 number(s): "695555486"

Test #41:

score: 0
Accepted
time: 100ms
memory: 45152kb

input:

351715
120661 101781 129273
142995 80157 128563
169330 148880 33505

output:

466480620

result:

ok 1 number(s): "466480620"

Test #42:

score: 0
Accepted
time: 193ms
memory: 78252kb

input:

905498
381722 200474 323302
202271 344030 359197
350698 364396 190404

output:

346377686

result:

ok 1 number(s): "346377686"

Test #43:

score: 0
Accepted
time: 355ms
memory: 98184kb

input:

1064626
261709 325862 477055
516569 367130 180927
307746 452237 304643

output:

557495758

result:

ok 1 number(s): "557495758"

Test #44:

score: 0
Accepted
time: 16ms
memory: 20648kb

input:

494104
224009 132488 137607
15527 180865 297712
203418 197294 93392

output:

0

result:

ok 1 number(s): "0"

Test #45:

score: 0
Accepted
time: 20ms
memory: 21976kb

input:

1153008
315731 708637 128640
128519 347757 676732
267014 535519 350475

output:

0

result:

ok 1 number(s): "0"

Test #46:

score: 0
Accepted
time: 368ms
memory: 115700kb

input:

1470490
550743 481409 438338
763576 96662 610252
363836 262517 844137

output:

964914867

result:

ok 1 number(s): "964914867"

Test #47:

score: 0
Accepted
time: 100ms
memory: 51800kb

input:

476270
72377 235854 168039
1528 311122 163620
254184 15707 206379

output:

0

result:

ok 1 number(s): "0"

Test #48:

score: 0
Accepted
time: 17ms
memory: 21712kb

input:

787189
201940 129464 455785
243491 290356 253342
257543 326980 202666

output:

0

result:

ok 1 number(s): "0"

Test #49:

score: 0
Accepted
time: 17ms
memory: 22096kb

input:

1311581
662049 427399 222133
182392 768551 360638
257311 534768 519502

output:

0

result:

ok 1 number(s): "0"

Test #50:

score: 0
Accepted
time: 60ms
memory: 35336kb

input:

215077
105142 95920 14015
37417 106030 71630
97785 86292 31000

output:

0

result:

ok 1 number(s): "0"

Test #51:

score: 0
Accepted
time: 16ms
memory: 21980kb

input:

680614
190222 59142 431250
229277 326583 124754
244226 267501 168887

output:

0

result:

ok 1 number(s): "0"

Test #52:

score: 0
Accepted
time: 16ms
memory: 20544kb

input:

599441
163256 359629 76556
269072 153998 176371
296850 273987 28604

output:

0

result:

ok 1 number(s): "0"

Test #53:

score: 0
Accepted
time: 21ms
memory: 21988kb

input:

1186565
664884 314828 206853
50093 597130 539342
352770 117639 716156

output:

0

result:

ok 1 number(s): "0"

Test #54:

score: 0
Accepted
time: 21ms
memory: 21308kb

input:

399589
160429 157151 82009
52807 151045 195737
168413 46646 184530

output:

0

result:

ok 1 number(s): "0"

Test #55:

score: 0
Accepted
time: 98ms
memory: 52604kb

input:

498263
277597 129082 91584
146928 169294 182041
198001 220974 79288

output:

20392590

result:

ok 1 number(s): "20392590"

Test #56:

score: 0
Accepted
time: 370ms
memory: 107732kb

input:

1287548
598441 439788 249319
532780 427274 327494
984985 96121 206442

output:

157485795

result:

ok 1 number(s): "157485795"

Test #57:

score: 0
Accepted
time: 17ms
memory: 21648kb

input:

1435275
447804 724373 263098
383152 619901 432222
383304 68399 983572

output:

0

result:

ok 1 number(s): "0"

Test #58:

score: 0
Accepted
time: 20ms
memory: 20956kb

input:

699090
240262 213752 245076
255039 260728 183323
234619 115480 348991

output:

0

result:

ok 1 number(s): "0"

Test #59:

score: 0
Accepted
time: 20ms
memory: 21876kb

input:

972438
478545 285919 207974
128489 319801 524148
286253 298521 387664

output:

0

result:

ok 1 number(s): "0"

Test #60:

score: 0
Accepted
time: 16ms
memory: 20796kb

input:

331352
121624 30247 179481
80755 93304 157293
62835 160621 107896

output:

0

result:

ok 1 number(s): "0"

Test #61:

score: 0
Accepted
time: 20ms
memory: 21944kb

input:

425318
161870 195187 68261
58421 111518 255379
98211 149256 177851

output:

0

result:

ok 1 number(s): "0"

Test #62:

score: 0
Accepted
time: 20ms
memory: 20476kb

input:

592741
319914 259579 13248
148647 194672 249422
378967 175386 38388

output:

0

result:

ok 1 number(s): "0"

Test #63:

score: 0
Accepted
time: 183ms
memory: 64100kb

input:

602228
34962 454429 112837
247881 315495 38852
384357 69191 148680

output:

0

result:

ok 1 number(s): "0"

Test #64:

score: 0
Accepted
time: 21ms
memory: 21816kb

input:

610389
373522 193737 43130
62839 130072 417478
138346 203349 268694

output:

0

result:

ok 1 number(s): "0"

Test #65:

score: 0
Accepted
time: 50ms
memory: 33884kb

input:

161360
82645 44242 34473
66788 59603 34969
48139 22450 90771

output:

559061811

result:

ok 1 number(s): "559061811"

Test #66:

score: 0
Accepted
time: 10ms
memory: 21120kb

input:

591506
92336 192103 307067
13873 290990 286643
28921 254667 307918

output:

0

result:

ok 1 number(s): "0"

Test #67:

score: 0
Accepted
time: 191ms
memory: 78872kb

input:

940718
486143 39848 414727
438813 358245 143660
200948 304832 434938

output:

189368763

result:

ok 1 number(s): "189368763"

Test #68:

score: 0
Accepted
time: 17ms
memory: 21968kb

input:

585970
36092 336501 213377
217719 134212 234039
454324 31689 99957

output:

0

result:

ok 1 number(s): "0"

Test #69:

score: 0
Accepted
time: 16ms
memory: 21520kb

input:

814985
350619 424060 40306
318150 477415 19420
296376 381374 137235

output:

0

result:

ok 1 number(s): "0"

Test #70:

score: 0
Accepted
time: 350ms
memory: 104400kb

input:

1212624
635151 355933 221540
382996 340761 488867
28683 189420 994521

output:

0

result:

ok 1 number(s): "0"

Test #71:

score: 0
Accepted
time: 16ms
memory: 20676kb

input:

825460
28354 541876 255230
334422 299199 191839
166016 391674 267770

output:

0

result:

ok 1 number(s): "0"

Test #72:

score: 0
Accepted
time: 20ms
memory: 20052kb

input:

644697
305286 296842 42569
165080 234255 245362
127688 459557 57452

output:

0

result:

ok 1 number(s): "0"

Test #73:

score: 0
Accepted
time: 20ms
memory: 21596kb

input:

604964
3223 299494 302247
292154 126107 186703
77013 270881 257070

output:

0

result:

ok 1 number(s): "0"

Test #74:

score: 0
Accepted
time: 21ms
memory: 21404kb

input:

3
0 1 2
1 1 1
1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #75:

score: 0
Accepted
time: 20ms
memory: 23456kb

input:

4
2 0 2
2 1 1
2 2 0

output:

24

result:

ok 1 number(s): "24"

Test #76:

score: 0
Accepted
time: 12ms
memory: 21408kb

input:

2
1 1 0
1 0 1
0 2 0

output:

0

result:

ok 1 number(s): "0"

Test #77:

score: 0
Accepted
time: 20ms
memory: 22336kb

input:

3
2 1 0
0 1 2
1 2 0

output:

0

result:

ok 1 number(s): "0"

Test #78:

score: 0
Accepted
time: 16ms
memory: 20216kb

input:

3
0 1 2
1 0 2
0 1 2

output:

0

result:

ok 1 number(s): "0"

Test #79:

score: 0
Accepted
time: 16ms
memory: 20184kb

input:

2
0 2 0
1 0 1
0 1 1

output:

0

result:

ok 1 number(s): "0"

Test #80:

score: 0
Accepted
time: 20ms
memory: 21196kb

input:

4
1 2 1
0 2 2
0 2 2

output:

0

result:

ok 1 number(s): "0"

Test #81:

score: 0
Accepted
time: 20ms
memory: 22028kb

input:

1
0 0 1
0 0 1
0 1 0

output:

0

result:

ok 1 number(s): "0"

Test #82:

score: 0
Accepted
time: 19ms
memory: 20736kb

input:

3
1 0 2
1 2 0
2 1 0

output:

0

result:

ok 1 number(s): "0"

Test #83:

score: 0
Accepted
time: 17ms
memory: 22936kb

input:

3
0 1 2
2 0 1
0 1 2

output:

6

result:

ok 1 number(s): "6"

Test #84:

score: 0
Accepted
time: 16ms
memory: 20708kb

input:

3
1 1 1
2 0 1
0 1 2

output:

0

result:

ok 1 number(s): "0"

Test #85:

score: 0
Accepted
time: 21ms
memory: 21784kb

input:

4
1 1 2
1 1 2
2 1 1

output:

0

result:

ok 1 number(s): "0"

Test #86:

score: 0
Accepted
time: 14ms
memory: 21624kb

input:

2
0 2 0
1 0 1
2 0 0

output:

0

result:

ok 1 number(s): "0"

Test #87:

score: 0
Accepted
time: 20ms
memory: 20156kb

input:

2
0 0 2
1 0 1
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #88:

score: 0
Accepted
time: 16ms
memory: 21740kb

input:

2
0 1 1
0 2 0
2 0 0

output:

0

result:

ok 1 number(s): "0"

Test #89:

score: 0
Accepted
time: 15ms
memory: 20676kb

input:

3
2 0 1
1 1 1
1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #90:

score: 0
Accepted
time: 11ms
memory: 22548kb

input:

5
1 2 2
1 2 2
1 2 2

output:

270

result:

ok 1 number(s): "270"

Test #91:

score: 0
Accepted
time: 15ms
memory: 21736kb

input:

3
2 1 0
1 0 2
0 1 2

output:

0

result:

ok 1 number(s): "0"

Test #92:

score: 0
Accepted
time: 21ms
memory: 21896kb

input:

3
2 1 0
1 0 2
1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #93:

score: 0
Accepted
time: 16ms
memory: 20268kb

input:

4
2 1 1
1 2 1
0 2 2

output:

0

result:

ok 1 number(s): "0"

Test #94:

score: 0
Accepted
time: 16ms
memory: 21636kb

input:

2
0 1 1
2 0 0
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #95:

score: 0
Accepted
time: 12ms
memory: 20944kb

input:

2
2 0 0
1 1 0
2 0 0

output:

0

result:

ok 1 number(s): "0"

Test #96:

score: 0
Accepted
time: 17ms
memory: 21844kb

input:

4
2 1 1
1 2 1
1 2 1

output:

0

result:

ok 1 number(s): "0"

Test #97:

score: 0
Accepted
time: 21ms
memory: 23088kb

input:

3
2 1 0
1 1 1
1 2 0

output:

6

result:

ok 1 number(s): "6"

Test #98:

score: 0
Accepted
time: 20ms
memory: 21520kb

input:

2
0 2 0
1 0 1
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #99:

score: 0
Accepted
time: 17ms
memory: 21940kb

input:

2
0 0 2
2 0 0
2 0 0

output:

0

result:

ok 1 number(s): "0"

Test #100:

score: 0
Accepted
time: 20ms
memory: 22852kb

input:

2
1 0 1
0 0 2
0 1 1

output:

2

result:

ok 1 number(s): "2"

Test #101:

score: 0
Accepted
time: 21ms
memory: 21972kb

input:

2
0 0 2
2 0 0
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #102:

score: 0
Accepted
time: 12ms
memory: 20956kb

input:

3
1 0 2
0 1 2
2 1 0

output:

0

result:

ok 1 number(s): "0"