// {{{ y0105w49 template 22K18 // hi mom #ifndef NULL #ifdef ARST #if (defined(__clang__)) #include #elif (defined(__GNUC__)) // #include #include #include #define EXTS #else #error "unsupported" #endif #else #ifndef _GLIBCXX_NO_ASSERT #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __cplusplus >= 201103L #include #include #include // #include #include #include #include // #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __cplusplus >= 201103L #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #endif #if __cplusplus >= 201402L #include #endif #if __cplusplus >= 201703L #include #include // #include #include #include // #include #include #include #endif #if __cplusplus >= 202002L #include #include #include #include #if __cpp_impl_coroutine # include #endif #include #include #include #include // #include #include // #include // #include #include #endif #if __cplusplus > 202002L // #include // #include #if __has_include() # include #endif #include #endif #endif #endif using namespace std; #ifdef ARST #define JO 1 #define OJ 0 #else #define JO 0 #define OJ 1 #endif #define STR(x) #x #define GCCDIAG(s) _Pragma(STR(GCC diagnostic s)) static_assert(true) #define Wsave GCCDIAG(push) #define Wpop GCCDIAG(pop) #define Wsupp(w) GCCDIAG(ignored "-W" w) #define Wpush(w) Wsave; Wsupp(w) #define typeof __typeof__ namespace gbd_ns { template struct is_iterable { template static long check(...); template static char check(int,typename T::const_iterator = C().end()); enum { value = sizeof(check(0)) == sizeof(char), neg_value = sizeof(check(0)) != sizeof(char) }; }; template struct _gbd3C; template ostream &_gbd3(ostream &os,const T &x) { return _gbd3C::call(os,x); } template<> ostream &_gbd3(ostream &os,const string &x) { return os<<'"'< ostream &_gbd3(ostream &os,char *const &x) { return os<<'"'< ostream &_gbd3_5(ostream &os,const T &x) { return _gbd3(os,x); } template ostream &_gbd4(ostream &os,const pair &p) { _gbd3(os<<'(',p.first); _gbd3(os<<',',p.second); return os<<')'; } template struct _gbd4_tupleC { static void call(ostream &os,const T &t) { _gbd4_tupleC::call(os,t); os<<','<(t); } }; template struct _gbd4_tupleC { static void call(ostream &os,const T &t) { os<(t); } }; template ostream &_gbd4(ostream &os,const tuple &t) { os<<'('; _gbd4_tupleC,sizeof...(Types)>::call(os,t); return os<<')'; } template<> ostream &_gbd4(ostream &os,const tuple<> &t) { (void)t; return os<<"()"; } template ostream &_gbd4(ostream &os,const T &x) { return os< struct _gbd3C { template static ostream &call(ostream &os,enable_if_t::value,const T> &V) { os<<"{"; bool ff=0; for(const auto &E:V) _gbd3_5(ff?os<<",":os,E), ff=1; return os<<"}"; } template static ostream &call(ostream &os,enable_if_t::neg_value,const T> &x) { return _gbd4(os,x); } }; template ostream &_gbd2(ostream &os,bool,vector::iterator nm,const T &x,Args&&... args); ostream &_gbd2(ostream &os,bool,vector::iterator) { return os; } template ostream &_gbd2(ostream &os,bool fi,vector::iterator nm,const char *x,Args&&... args) { return _gbd2(os<<(fi?"":" ")< ostream &_gbd2(ostream &os,bool fi,vector::iterator nm,const T &x,Args&&... args) { return _gbd2(_gbd3(os<<(fi?"":" ")<<*nm<<"=",x),0,nm+1,args...); } vector split(string s) { vector Z; string z=""; s+=','; int dep=0; for(char c:s) { if(c==',' && !dep) Z.push_back(z),z=""; else z+=c; if(c=='(' || c=='{' || c=='[') ++dep; if(c==')' || c=='}' || c==']') --dep; } return Z; } template ostream &_gbd1(ostream &os,const string &nm,Args&&... args) { return _gbd2(os,1,split(nm).begin(),args...); } template string _gbd1(const string &nm,Args&&... args) { ostringstream oss; _gbd2(oss,1,split(nm).begin(),args...); return oss.str(); } } bool DBG=1,EMACS=0; #define dbg(...) (JO&&DBG?gbd_ns::_gbd1(cerr<<"\033[38;5;5m"<<__FILE__<<":"<<__LINE__<<(EMACS?":note: ":": "),#__VA_ARGS__,__VA_ARGS__)<<"\033[0m"< struct _y_combinator_result { Fun _fun; template explicit _y_combinator_result(T &&fun) : _fun(forward(fun)) {} template decltype(auto) operator()(Args &&... args) { return _fun(ref(*this),forward(args)...); } }; template [[nodiscard]] decltype(auto) fix(Fun &&fun) { return _y_combinator_result>(forward(fun)); } #define nop void() #define sz(x) (int((x).size())) #define all(v) (v).begin(),(v).end() #define sortu(v) (sort(all(v)), (v).resize(unique(all(v))-begin(v))) #define forenum(i,...) for(int i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else #define forenumll(i,...) for(long long i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else #define forbs(k,i,bs) for(ptrdiff_t k=0,i=(bs)._Find_first();i<(ptrdiff_t)(bs).size();i=(bs)._Find_next(i),++k) #define fordbs(k,i,bs) for(ptrdiff_t k=0,i=(bs).find_first();i<(ptrdiff_t)(bs).size();i=(bs).find_next(i),++k) #define get(x,i) get(x) template bool inb(const T &x,const T &l,const T &r) { return l<=x&&x<=r; } #define fi first #define se second #define pb push_back #define eb emplace_back #ifdef EXTS template using omap=__gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template using oset=omap; template using rope=__gnu_cxx::rope; using dbitset=tr2::dynamic_bitset<>; #endif constexpr int e0=1, e1=10, e2=100, e3=1000; constexpr int e4=10*e3, e5=100*e3, e6=1000*e3; constexpr int e7=10*e6, e8=100*e6, e9=1000*e6; constexpr long long e10=10LL*e9, e11=100LL*e9, e12=1000LL*e9; constexpr long long e13=10*e12, e14=100*e12, e15=1000*e12; constexpr long long e16=10*e15, e17=100*e15, e18=1000*e15; constexpr __int128_t e21=__int128_t(e3)*e18, e24=__int128_t(e6)*e18, e27=__int128_t(e9)*e18; constexpr __int128_t e30=e3*e27, e33=e6*e27, e36=e9*e27; using ulll=__uint128_t; using lll=__int128_t; using ull=unsigned long long; using ll=long long; using ld=long double; #ifdef EXTS using lld=__float128; #endif long long START_TIME=chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count(); inline long long now_U_03BC_s() { return chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count()-START_TIME; } const char *fmt_time(long long U_03BC_s=now_U_03BC_s()) { static char dur[20]; sprintf(dur,"%llu.%03llus",U_03BC_s/e6,(U_03BC_s%e6)/e3); return dur; } #define timed(cb) do { dbg("timed "#cb" ..."); unsigned long long start=now_U_03BC_s(); cb; dbg("timed "#cb" took",fmt_time(now_U_03BC_s()-start)); } while(0) int arg1; bool inp; vector args; unsigned seed=unsigned(JO&&getenv("sd")?atoi(getenv("sd")):OJ?START_TIME:START_TIME%e5); mt19937 igen(seed<<1),gen(seed<<1|1); #define irand(...) _rand(igen,__VA_ARGS__) #define rand(...) _rand(gen,__VA_ARGS__) template enable_if_t::is_integer,T> _rand(mt19937 &g,T l,T r) { return uniform_int_distribution(l,r)(g); } template enable_if_t::is_integer,T> _rand(mt19937 &g,T n) { return _rand(g,T(1),n); } [[deprecated]] int _rand(mt19937 &g) { return _rand(g,0,numeric_limits::max()); } template enable_if_t::is_iec559,T> _rand(mt19937 &g,T l,T r) { return uniform_real_distribution(l,r)(g); } bool _rand(mt19937 &g,double p) { return bernoulli_distribution(p)(g); } template T _rand(mt19937 &g,initializer_list il) { return *(il.begin()+_rand(g,0,(int)il.size()-1)); } template T _rand(mt19937 &g,double p,T a,T b) { return _rand(g,p)?a:b; } template T _rand(mt19937 &g,initializer_list il,initializer_list wt) { assert(il.size()==wt.size()); return *(il.begin()+discrete_distribution(wt)(g)); } #define random_shuffle(...) static_assert(false,"random_shuffle deprecated, use shuffle") #define ine(x,e) (inp?cin>>(x),nop:((x)=(e),nop)) #define inr(x,...) ine(x,irand(__VA_ARGS__)) #define endl '\n' string garb; void exit0() { DBG=1; dbgt("gg (early)"); exit(0); } #ifndef MAIN #define MAIN _main #endif void MAIN(); int32_t main([[maybe_unused]]int argc,[[maybe_unused]]char *argv[]) { ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios_base::failbit | ios_base::badbit); arg1=0,args={argv,argv+argc}; if(sz(args)>1) { if(args[1][0]=='i') freopen((string(__FILE__).substr(0,string(__FILE__).find('.'))+"."+args[1].substr(1)+".in").c_str(),"r",stdin); else if(args[1][0]=='I') freopen(args[1].substr(1).c_str(),"r",stdin); else arg1=stoi(args[1]); } inp=!arg1; if(JO && getenv("EMACS")) EMACS=1; dbgt(arg1,seed,args); #ifdef QUIET DBG=0; #endif MAIN(); DBG=1; dbgt("gg;wp"); } constexpr int inf=e9+99; constexpr ll linf=1LL*e9*e9+99; #if __cplusplus >= 202002L constexpr long double U_03C4__ld=2*numbers::pi_v; #else const long double U_03C4__ld=2*acosl(-1); #endif #define U_03C4_ ((flt)U_03C4__ld) constexpr long double U_03B5__ld=1e-8l; #define U_03B5_ ((flt)U_03B5__ld) // }}} using flt=double; //CARE constexpr int P=e9+7;//998'244'353; #if __cplusplus < 202002L #define popcount __builtin_popcount #define countr_zero __builtin_ctz #endif void _main() { /* CURSOR START */ int n,k; ine(n,arg1), inr(k,{2,3,10,10,10}); dbg(n,k); const int N=e3,K=10; assert(inb(n,2,N)); assert(inb(k,2,K)); auto f=[&](int d,unsigned mk) -> const vector & { static vector dp[K][1<<(K-1)]; d=min(d,k); auto &ans=dp[d-1][mk]; if(sz(ans)) return ans; vector rel={0,d}; forbs(_,i,bitset(mk)) rel.pb(d+int(i+1)); for(int &x:rel) x=n-x; for(int x:rel) { flt Z=0; for(int y:rel) { if(x==y) continue; for(int l=x;l=r) gd=0; if(!gd) continue; #if 0 flt Z2=0; constexpr int C=8192; for(int it=C;~--it;) { flt xx=l+flt(it*2+1)/(2*C); flt Z3=min(flt(1),((y+k)-xx)/k); for(int z:rel) if(z!=x && z!=y) Z3*=min(flt(1),(xx-z)/k); Z2+=Z3; } Z2/=C; Z+=Z2/k; #else vector P={1}; if(y<=l) P={flt((y+k)-l)/k,flt(-1)/k}; for(int z:rel) if(z!=x && z!=y && z+k>=r) { P.pb(0); for(int i=sz(P)-1;~--i;) P[i+1]+=P[i], P[i]*=-(z-l); for(auto &a:P) a/=k; } flt Z3=0; forenum(i,flt a:P) Z3+=a/(i+1); // dbg(Z2,Z3,P); Z+=Z3/k; #endif } } ans.pb(Z); } if((k<0;sd2--) { auto &odp=dp[sd2%(k+1)]; for(int sd1=min(n,sd2+k);sd1>sd2;sd1--) { for(unsigned mk=1<>(sd2-nsd2); if(u