#pragma GCC optimize("Ofast") #pragma GCC target("avx2") #define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);}) #define wt(v) ({ulong _z=v;do*--wp=_z%10+48;while(_z/=10);}) #define wt1(v) ({char wbuf[64],*wp=wbuf+sizeof wbuf;wt(v);write(1,wp,wbuf+sizeof wbuf-wp);}) #define rep(v,e) for(typeof(e)v=0;v=0;){ ++a[c]; ++b; } ulong z=1; rep(i,10){ z=z*fac[a[i]>>10]%MD; reps(j,a[i]&~0x3ff,a[i]){ z=z*(j+1)%MD; } } z=inverse(z); z=z*fac[b>>10]%MD; reps(j,b-1&~0x3ff,b-1){ z=z*(j+1)%MD; } z=z*(b-a[0])%MD; wt1(z); _exit(0); }