#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const ll mod=;

const int N=;

ll n,m;

ll fac[N];

ll qpow(ll a,ll b)

{

    ll res=;a=a%mod;

    while(b)

    {

        if(b&)res=res*a%mod;

        a=a*a%mod;

        b>>=;

    }

    return res;

}

ll C(ll x,ll y)

{

    if(y>x)return ;

    return fac[x]*(qpow(fac[y]*fac[x-y]%mod,mod-))%mod;

}

ll lucas(ll x,ll y)

{

    if(!y)return ;

    return C(x%mod,y%mod)*lucas(x/mod,y/mod)%mod;

}

void ini()

{

    fac[]=;

    for(ll i=;i<=m+n;i++)

        fac[i]=fac[i-]*1LL*i%mod;

}

int main()

{

    scanf("%lld%lld",&n,&m);

    ini();

    ll ans=(lucas(m+n,m)-lucas(m+n,m-)+mod)%mod;

    cout<<ans<<endl;

    return ;

}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdlib>

using namespace std;

typedef long long ll;

#define pa pair<ll,ll>

const int N=;

int n,m,tot,rest,now;

ll x,w[N],a[N],num[N],cnt,total,ans;

pa bu[N];

namespace bit

{

    ll c[N];

    int lb(int x){return x&-x;}

    void add(int x)

    {

        for( ;x<=n;x+=lb(x))

            c[x]++;

    }

    int ask(int x)

    {

        int res=;

        for( ;x;x-=lb(x))

            res+=c[x];

        return res;

    }

}

int main()

{

    scanf("%d%d%lld",&n,&m,&x);

    for(int i=;i<=n;i++)

        scanf("%lld",&w[i]);

    for(int i=;i<=n;i++)

        scanf("%lld",&a[i]);

    for(int i=;i<=n;i++)

        if(x>=w[i])bu[++tot]=make_pair((x-w[i])/a[i]+,tot);

    sort(bu+,bu+tot+);

    rest=tot;

    for(int i=;i<=tot;i++)

    {

        int l=,r=m-now;

        while(l<=r)

        {

            int mid=l+r>>;

            if(1LL*rest*mid<bu[i].first-total)l=mid+,cnt=mid;

            else r=mid-;

        }

        if(now+cnt==m)

        {

            ans+=(tot-i+)*m;

            cout<<ans<<endl;

            exit();

        }

        num[i]=now+cnt;

        int pre=bu[i].second-bit::ask(bu[i].second);

        bit::add(bu[i].second);

        if(bu[i].first-rest*cnt-total>=pre)total++,num[i]++;

        total+=cnt*rest,now+=cnt;

        rest--;

        ans+=num[i];

    }

    cout<<ans<<endl;

    return ;

}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<vector>

#include<queue>

#include<algorithm>

using namespace std;

const int M=,N=1e5+;

int read()

{

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

    while(isdigit(ch))x=x*+ch-'',ch=getchar();

    return x*f;

}

struct room_

{

    int x,y,op;

}a[N];

int n,R,C;

vector<int> h[M],l[M],g[N];

int tot,head[M<<],nxt[M<<],to[M<<],deg[N],ans[N];

void add(int x,int y)

{

    to[++tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

}

int dfn[N],low[N],st[N],top=,vis[N],bel[N],scc,ind,size[N];

void tarjan(int x)

{

    dfn[x]=low[x]=++ind;

    vis[x]=;

    st[++top]=x;

    for(int i=head[x];i;i=nxt[i])

    {

        int y=to[i];

        if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]);

        else if(vis[y])low[x]=min(low[x],dfn[y]);

    }

    if(low[x]==dfn[x])

    {

        scc++;int now=;

        do

        {

            now=st[top--];

            size[scc]++;

            bel[now]=scc;

            vis[now]=;

        }while(now!=x);

    }

}

int main()

{

    n=read();R=read();C=read();

    for(int i=;i<=n;i++)

    {

        a[i].x=read(),a[i].y=read(),a[i].op=read();

        h[a[i].x].push_back(i);l[a[i].y].push_back(i);

    }

    for(int i=;i<=n;i++)

    {

        int op=a[i].op;

        if(op==)

        {

            int sz=h[a[i].x].size();

            for(int j=;j<sz;j++)

            {

                if(h[a[i].x][j]==i)continue;

                add(i,h[a[i].x][j]);

            }

        }

        else if(op==)

        {

            int sz=l[a[i].y].size();

            for(int j=;j<sz;j++)

            {

                if(l[a[i].y][j]==i)continue;

                add(i,l[a[i].y][j]);

            }

        }

        else if(op==)

        {

            int sz;

            if(a[i].x>)

            {

                sz=h[a[i].x-].size();

                for(int j=;j<sz;j++)

                {

                    if(a[h[a[i].x-][j]].y>=a[i].y-&&a[h[a[i].x-][j]].y<=a[i].y+)

                        add(i,h[a[i].x-][j]);

                }

            }

            sz=h[a[i].x].size();

            for(int j=;j<sz;j++)

            {

                if(h[a[i].x][j]==i)continue;

                if(a[h[a[i].x][j]].y>=a[i].y-&&a[h[a[i].x][j]].y<=a[i].y+)

                    add(i,h[a[i].x][j]);

            }

            if(a[i].x<R)

            {

                sz=h[a[i].x+].size();

                for(int j=;j<sz;j++)

                {

                    int now=h[a[i].x+][j];

                    if(a[now].y>=a[i].y-&&a[now].y<=a[i].y+)

                        add(i,now);

                }

            }

        }

    }

    for(int i=;i<=n;i++)

        if(!dfn[i])tarjan(i);

    for(int x=;x<=n;x++)

        for(int i=head[x];i;i=nxt[i])

        {

            int y=to[i];

            if(bel[y]!=bel[x])

                g[bel[x]].push_back(bel[y]),deg[bel[y]]++;

        }

    //debug();

    //puts("----------------------------------------");

/*    for(int i=1;i<=scc;i++)

        if(!v[i])

        {

            num=0,dfs(i);

        }*/

    queue<int> q;

    for(int i=;i<=scc;i++)

        if(!deg[i])q.push(i),ans[i]=size[i];

    while(!q.empty())

    {

        int x=q.front();

        q.pop();int sz=g[x].size();

        for(int i=;i<sz;i++)

        {

            int y=g[x][i];

            ans[y]=max(ans[y],ans[x]+size[y]);

            if(!(--deg[y]))q.push(y);

        }

    }

    cout<<*max_element(ans+,ans++scc)<<endl;

    return ;

}