#include #if __has_include() #include #endif using namespace std; using ll = long long; using ull = unsigned long long int; using i128 = __int128_t; using pii = pair; using pll = pair; using ld = long double; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; using vi = vc; using vl = vc; using vpi = vc; using vpl = vc; template using pq = priority_queue; template using pqg = priority_queue, greater>; #define overload5(a, b, c, d, e, name, ...) name #define overload4(a, b, c, d, name, ...) name #define REP0(n) for(ll jidlsjf = 0; jidlsjf < n; ++jidlsjf) #define REP1(i, n) for(ll i = 0; i < (n); ++i) #define REP2(i, a, b) for(ll i = (a); i < (b); ++i) #define REP3(i, a, b, c) for(ll i = (a); i < (b); i += (c)) #define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__) #define per0(n) for(int jidlsjf = 0; jidlsjf < (n); ++jidlsjf) #define per1(i, n) for(ll i = (n)-1; i >= 0; --i) #define per2(i, a, b) for(ll i = (a)-1; i >= b; --i) #define per3(i, a, b, c) for(ll i = (a)-1; i >= (b); i -= (c)) #define per(...) overload4(__VA_ARGS__, per3, per2, per1, per0)(__VA_ARGS__) #define fore0(a) rep(a.size()) #define fore1(i, a) for(auto &&i : a) #define fore2(a, b, v) for(auto &&[a, b] : v) #define fore3(a, b, c, v) for(auto &&[a, b, c] : v) #define fore4(a, b, c, d, v) for(auto &&[a, b, c, d] : v) #define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__) #define perm(v) for(bool permrepflag = true; (permrepflag ? exchange(permrepflag, false) : next_permutation(all(v)));) #define fi first #define se second #define pb push_back #define ppb pop_back #define ppf pop_front #define eb emplace_back #define drop(s) cout << #s << endl, exit(0) #define si(c) (int)(c).size() #define lb(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{})) #define ub(c, x) distance((c).begin(), upper_bound(all(c), (x))) #define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{})) #define rng(v, l, r) v.begin() + (l), v.begin() + (r) #define all(c) begin(c), end(c) #define rall(c) rbegin(c), rend(c) #define SORT(v) sort(all(v)) #define RSORT(v) sort(rall(v)) #define REV(v) reverse(all(v)) #define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end()) template T SUM(const S &v) { return accumulate(all(v), T(0)); } #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define INT(...) \ int __VA_ARGS__; \ IN(__VA_ARGS__) #define INTd(...) \ int __VA_ARGS__; \ IN2(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ IN(__VA_ARGS__) #define LLd(...) \ ll __VA_ARGS__; \ IN2(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ IN(__VA_ARGS__) #define CHR(...) \ char __VA_ARGS__; \ IN(__VA_ARGS__) #define LD(...) \ ld __VA_ARGS__; \ IN(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ IN(name) #define VECd(type, name, size) \ vector name(size); \ IN2(name) #define VEC2(type, name1, name2, size) \ vector name1(size), name2(size); \ for(int i = 0; i < size; i++) IN(name1[i], name2[i]) #define VEC2d(type, name1, name2, size) \ vector name1(size), name2(size); \ for(int i = 0; i < size; i++) IN2(name1[i], name2[i]) #define VEC3(type, name1, name2, name3, size) \ vector name1(size), name2(size), name3(size); \ for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i]) #define VEC3d(type, name1, name2, name3, size) \ vector name1(size), name2(size), name3(size); \ for(int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i]) #define VEC4(type, name1, name2, name3, name4, size) \ vector name1(size), name2(size), name3(size), name4(size); \ for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i], name4[i]); #define VEC4d(type, name1, name2, name3, name4, size) \ vector name1(size), name2(size), name3(size), name4(size); \ for(int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i], name4[i]); #define VV(type, name, h, w) \ vector> name(h, vector(w)); \ IN(name) #define VVd(type, name, h, w) \ vector> name(h, vector(w)); \ IN2(name) int scan() { return getchar(); } void scan(int &a) { cin >> a; } void scan(long long &a) { cin >> a; } void scan(char &a) { cin >> a; } void scan(ld &a) { cin >> a; } void scan(string &a) { cin >> a; } template void scan(pair &p) { scan(p.first), scan(p.second); } template void scan(vector &); template void scan(vector &a) { for(auto &i : a) scan(i); } template void scan(T &a) { cin >> a; } void IN() {} void IN2() {} template void IN(Head &head, Tail &...tail) { scan(head); IN(tail...); } template void IN2(Head &head, Tail &...tail) { scan(head); --head; IN2(tail...); } template void prt_(T a){ cout< void prt_(pair a){ cout<<"{"< void prt(vc a){ for(size_t i=0;i void prt(vvc a){ for(auto& v:a){ for(size_t i=0;i void prt(T a){ prt_(a),cout<<"\n"; } template void prt(T a,Args... args){ prt_(a),cout<<" ",prt(args...); } template struct multi_dim_vector{ using type=vc::type>; }; template struct multi_dim_vector{ using type=T; }; template vc mvec(int n,Arg&& arg){ return vc(n,arg); } template class multi_dim_vector::type mvec(int n,Args&&... args){ return typename multi_dim_vector::type(n,mvec(args...)); } template T REVed(T a){ reverse(a.begin(),a.end()); return a; } template T SORTed(T a){ sort(a.begin(),a.end()); return a; } template T RSORTed(T a){ sort(a.rbegin(),a.rend()); return a; } vi iota(int n){ vi res(n); iota(res.begin(),res.end(),0); return res; } template bool chmax(T &a, T b){ return (a < b ? a = b, 1 : 0); } template bool chmin(T &a, T b){ return (a > b ? a = b, 1 : 0); } template auto runLength(T a) -> vc>{ int n=a.size(); vc> res; if(n==0){ return res; } typename decltype(a)::value_type now=a[0]; ll l=1; rep(i,1,n){ if(a[i-1]==a[i]){ l++; } else{ res.pb(now,l); now=a[i],l=1; } } res.pb(now,l); return res; } template struct mymodint{ ll x; static constexpr ll get_mod(){ return mod; } ll val(){ return x; } mymodint(ll x_=0):x((x_%mod+mod)%mod){} mymodint operator-(){ return (x==0)?0:mod-x; } mymodint operator+(mymodint rhs){ return mymodint(*this)+=rhs; } mymodint operator-(mymodint rhs){ return mymodint(*this)-=rhs; } mymodint operator*(mymodint rhs){ return mymodint(*this)*=rhs; } mymodint operator/(mymodint rhs){ return mymodint(*this)/=rhs; } mymodint pow(ll rhs){ mymodint res=1,now=(*this); while(rhs){ res*=((rhs&1)?now:1),now*=now,rhs>>=1; } return res; } mymodint& operator+=(mymodint rhs){ x+=rhs.x,x-=((x>=mod)?mod:0); return (*this); } mymodint& operator-=(mymodint rhs){ x-=rhs.x; x+=((x<0)?mod:0); return (*this); } mymodint& operator*=(mymodint rhs){ x=x*rhs.x%mod; return (*this); } mymodint& operator/=(mymodint rhs){ return (*this)*=rhs.pow(mod-2); } bool operator==(mymodint rhs){ return x==rhs.x; } bool operator!=(mymodint rhs){ return x!=rhs.x; } }; template using modint= #if __has_include() atcoder::static_modint; #else mymodint; #endif template std::ostream& operator<<(std::ostream& os,modint x){ return os<<(x.val()); } template std::istream& operator>>(std::istream& is,modint& x){ ll t; is>>t,x=t; return is; } template struct cmb{ vc fac,ifac; cmb(int mx=3000000):fac(mx+1,1),ifac(mx+1,1){ for(int i=1;i<=mx;++i){ fac[i]=fac[i-1]*i; } ifac[mx]/=fac[mx]; for(int i=mx;i>0;--i){ ifac[i-1]=ifac[i]*i; } } T operator()(ll n,ll k){ if(n<0||k<0||n; cmb C; INT(n,m); VEC(ll,b,n); vl c(n-1); c[0]=b[1]; rep(i,1,n-1){ c[i]=b[i+1]-b[i]; } auto f=mvec(n-1,m+1,0); rep(j,m+1){ f[0][j]=C.fi(j)*C.fi(j+b[0]-c[0]); } rep(i,1,n-1){ rep(j,0,m+1){ f[i][j]=C.fi(j)*C.fi(j-c[i]); } } vc g(m+1); g[0]=1; rep(i,n-1){ g=atcoder::convolution(f[i],g); g.resize(m+1); } int s=SUM(c); fp ans=0; rep(i,m+1){ ans+=g[i]*C.fi(b[0]-i)*C.fi(s-i); } prt((ans*C.f(b[0])*C.f(m-b[0])*C(m,b[0])).val()); }