#include #include using namespace std; using namespace atcoder; typedef long long int ll; typedef long double ld; typedef vector vi; typedef vector vl; typedef vector vvl; typedef vector vvvl; typedef vector vvvvl; typedef vector vb; typedef vector vvb; typedef vector vvvb; typedef vector vvvvb; typedef pair pl; typedef pair ppl; typedef pair pppl; typedef pair pppppl; #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(a) begin(a),end(a) #define sz(a) (int)(a).size() #define F first #define S second #define bs(A,x) binary_search(all(A),x) #define lb(A,x) (ll)(lower_bound(all(A),x)-A.begin()) #define ub(A,x) (ll)(upper_bound(all(A),x)-A.begin()) #define cou(A,x) (ll)(upper_bound(all(A),x)-lower_bound(all(A),x)) templateusing min_priority_queue=priority_queue,greater>; templatebool chmax(T&a,T b){if(abool chmin(T&a,T b){if(b vm; typedef vector vvm; typedef vector vvvm; typedef vector vvvvm; ostream&operator<<(ostream&os,mint a){os<>(istream&is,mint&a){int x;is>>x;a=mint(x);return is;} //*/ templateostream&operator<<(ostream&os,pairp){os<istream&operator>>(istream&is,pair&p){is>>p.F>>p.S;return is;} templateostream&operator<<(ostream&os,vectorv){rep(i,0,sz(v))os<istream&operator>>(istream&is,vector&v){for(T&in:v)is>>in;return is;} template vectorinv(const vector&f){ assert(f[0].val()); vectorg{f[0].inv()}; while(g.size()x(f.begin(),f.begin()+min(f.size(),2*g.size())); x=convolution(x,convolution(g,g)); g.resize(2*g.size()); for(int i=g.size()/2;i pair,vector>div(vectorf,const vector&g){ if(f.size()(0),f); reverse(f.begin(),f.end()); vectorh=g; reverse(h.begin(),h.end()); while(h.size()+g.size()<=f.size())h.emplace_back(0); vectorq=convolution(f,inv(h)); q.resize(f.size()-g.size()+1); reverse(q.begin(),q.end()); auto r=convolution(g,q); reverse(f.begin(),f.end()); for(int i=0;i vectormultipoint_evaluation(vectorf,vectorp){ int N=p.size(),n=1; while(n>seg(2*n,vector(1,1)); for(int i=0;i{-p[i],1}; for(int i=n-1;i;i--)seg[i]=convolution(seg[2*i],seg[2*i+1]); seg[1]=div(f,seg[1]).second; for(int i=1;ians(N); for(int i=0;i=0); if(!N)return 1; int n=sqrtl(N); mint ans=1; while(n*n>N)n--; while(N>n*n)ans*=N--; queue>que; for(int i=1;i<=n;i++)que.emplace(vector{i,1}); while(que.size()>1){ auto u=que.front();que.pop(); auto v=que.front();que.pop(); que.emplace(convolution(u,v)); } vectorp(n); for(int i=0;isync_with_stdio(0); cin.exceptions(cin.failbit); ll N,K;cin>>N>>K; chmin(K,N-K); if(N>=mod){ if(N-K