模板

inline int lowbit(int x)
{
    return x&-x;
}//lowbit

inline int ask(int x)
{
    int ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}//单点查询

inline void change(int x,int v)
{
    while(x<=N)
    {
        t[x]+=v;
        x+=lowbit(x);
    }
}//单点修改

inline int ask_all(int l,int r)
{
    return(ask(r)-ask(l-1));
}//区间查询

inline void change_all(int l,int r,int x)
{
    change(1,x);change(r+1,-x);
}//区间修改

inline void change(int p, int x)
{
    for(int i=p;i<=n;i+=i&-i)
        sum1[i]+=x,sum2[i]+=x*p;
}
inline void change_all(int l, int r, int x)
{
    change(l,x),change(r+1,-x);
}
inline int ask(int p)
{
    int ans=0;
    for(int i=p;i;i-= i&-i)
        ans+=(p+1)*sum1[i]-sum2[i];
    return ans;
}
inline int ask_all(int l, int r)
{
    return ask(r)-ask(l-1);
}

#define p<<1 ls
#define p<<1|1 rs
#define mid (l+r)>>1
inline void push_up(int p)
{
    t[p].pre=t[ls].pre+t[rs].pre;
    t[p].maxl=max(t[ls].maxl,t[ls].pre+t[rs].maxl);
    t[p].maxr=max(t[rs].maxr,t[rs].pre+t[ls].maxr);
    t[p].ans=max(max(t[ls].ans,t[rs].ans),t[ls].maxr+t[rs].maxl);
    return;
}
inline void bulid(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r) 
    {
        t[p].pre=a[l];
        return;
    }
    int mid=l+r>>1;
    bulid(ls,l,mid);
    bulid(rs,mid+1,r);
    t[p].pre=t[ls].pre+t[rs].pre;
    push_up(p);
}
inline void change(int p,int x,int y,int z)
{
    if(x<=t[p].l && y>=t[p].r)
    {
        t[p].pre+=(int)z*(t[p].r-t[p].l+1);
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) change(ls,x,y,z);
    if(y>mid) change(rs,x,y,z);
    t[p].pre=t[ls].pre+t[rs].pre;
    push_up(p);
} 
inline int find(int p,int x,int y)
{
    if(x<=t[p].l && y>=t[p].r) return t[p].pre;
    int mid=t[p].l+t[p].r>>1;
    int ans=0;
    if(x<=mid) ans+=find(ls,x,y);
    if(y>mid) ans+=find(rs,x,y);
    return ans;
} 

inline int read()
{
    int d=1,x=0;char ch;
    while(ch<'0'||ch>'9'){ch=getchar();if(ch=='-')d=-1;};
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();};
    return d*x;
}

inline void exgcd(int a,int b,int &x,int &y)
{
    if (!b)
    {
        x=1;
        y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
}//exgcd

inline int inv(int x)
{
    return (x%p+x)%p;
}//逆元

inline int gcd(int x,int y)
{
    return __gcd(x,y);
}//gcd
for(int i=1;i*i<=n;++i)
    {
        if(n%i) continue;
        prime[++cnt]=i;
        if(i*i!=n) prime[++cnt]=n/i;
    }
    //线性筛素数

inv[0]=inv[1]=1;
    for(int i=2;i<=n;++i)
       inv[i]=(p-p/i)*inv[p%i]%p;
    //线性处理逆元
inline int qpow(int a,int b,int p)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }  
    return ans;
}//快速幂

inline int p(int a,int b)
{
    int ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return ans%p;
}//龟速乘

inline void Euler(int n)
{
    vis[0]=vis[1]=1;
    for(register int i=2;i<=n;++i)
    {
        if(!vis[i]) 
        prime[++cnt]=i,phi[i]=i-1;
        for(register int j=1;j<=cnt && i*prime[j]<=n;++j)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}//线性筛欧拉函数

inline int Euler(int n)
{
    int a=n;
    for(int i=2;i*i<=n;++i)
    {
        if(n%i==0)
        {
            a=a/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) a=a/n*(n-1);
    return a;
}//求n以内欧拉函数总和

inline int lucas(int a,int b)
{
    if(a>b) return 0;
    if(b<=P) return fac[b]%P*ifac[a]%P*ifac[b-a]%P;
    return lucas(a%P,b%P)%P*lucas(a/P,b/P)%P;
}//Lucas定理

    js[0]=1;
    for(register int i=1;i<=n;++i)
        js[i]=js[i-1]*i%p;
    inv[n]=qpow(js[n],p-2);
    inv[0]=1;
    for(register int i=n-1;i>=1;--i)
        inv[i]=(inv[i+1]*(i+1))%p;
inline int C(int n,int m)
{
    return(((js[n]*inv[m])%p)*inv[n-m])%p;
}//预处理求组合数

    d[0]=1,d[1]=0,d[2]=1;
    for(register int i=3;i<=n;++i)
        d[i]=((i-1)*((d[i-1]+d[i-2])%p))%p;
        //错排

inline int CRT()
{
    int p=1,ans=0;
    for(int i=1;i<=n;++i)
        p*=mod[i];
    for(int i=1;i<=n;++i)
        (ans+=(p/mod[i])*inv(p/mod[i],mod[i])*r[i])%=p;
    return (ans%p+p)%p;
}

inline int exCRT()
{
    int p=mod[1];ans=a[1];
    int x,y,c,d;
    for(register int i=2;i<=n;++i)
    {
        x=y=0;
        c=(a[i]-ans%mod[i]+mod[i])%mod[i];
        d=exgcd(p,mod[i],x,y);
        if(!(c%d))
            ans+=(((x+mod[i])%mod[i])*(c/d)%mod[i])*p,
            p=p*mod[i]/gcd(p,mod[i]),
            ans=ans%p;
        else return -1;
    }
    return ans%p;
}//exCRT

inline int exlucas(int n,int m,int p)
{
    int P=p,tot=0;
    int Genshin=sqrt(p);
    for(int i=2;i<=Genshin;i++)
    {
        if(!(P%i))
        {
            int pk=1;
            while(!(P%i))
            {
                pk*=i;P/=i;
            }
            a[++tot]=pk;b[tot]=C(n,m,i,pk);
        }
    }
    if(P!=1)
    {
        a[++tot]=P;b[tot]=C(n,m,P,P);
    }
    int ans=0;
    for(int i=1;i<=tot;++i)
    {
        int M=p/a[i],t=inv(M,a[i]);
        ans=(ans+b[i]*M%p*t%p)%p;
    }
    return ans;
}//exLucas!