//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INF 100000000
#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define repp(i, n, s) for (int i = (int)(n); i >= (int)(s); i--)
#define mp make_pair
#define tp make_tuple
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef tuple<int,int,int> T;
typedef tuple<ll,ll,ll> TL;
ll mod = 1000000007;
ll mod2 = 998244353;

vector<vector<P>> G(100050);
vector<ll> ans(100050);
int n,m;

void dfs(int index){
    for (auto g : G[index]){
        int nv = g.first;
        int cv = g.second;
        if (ans[nv]==0){
            if (ans[index]==cv){
                if (cv + 1 >n) {
                    ans[nv] = 1;
                }else{
                    ans[nv] = cv + 1;
                }
                dfs(nv);
            }else{
                ans[nv] = cv;
                dfs(nv);
            }
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;

    rep(i,0,m){
        int a,b,c;cin>>a>>b>>c;
        a--;
        b--;
        G[a].push_back(mp(b,c));
        G[b].push_back(mp(a,c));
    }
    
    dfs(0);
    
    rep(i,0,n){
        cout<<ans[i]<<endl;
    }
}
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define per(i,a,b) for(int i = (a); i > (b); i--)
#define repl(i,a,b) for(ll i = (a); i < (b); i++)
#define perl(i,a,b) for(ll i = (a); i > (b); i--)
#define factinv invfact

const ll MOD = 1000000007;

const int MAX = 2000000;

long long fact[MAX+1], invfact[MAX+1];

//Fast modular exponentiation, needed by the function below
long long fast_exp(long long base, long long exp, long long mod) {
    long long res=1;
    while(exp>0) {
       if(exp%2==1) res=(res*base)%mod;
       base=(base*base)%mod;
       exp/=2;
    }
    return res%mod;
}

//Precomputes factorials and their inverses (modulo mod) from 0 to n
void binom(int n, long long mod){
    fact[0] = 1; invfact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = (fact[i-1]*i)%mod;
    }
    invfact[n] = fast_exp(fact[n], mod-2, mod);
    for(int i = n-1; i >= 0; i--){
        invfact[i] = ((i+1)*invfact[i+1])%mod;
    }
}

void solve(){
    binom(MAX, MOD);
    int n, m, k;
    cin >> n >> m >> k;
    if(n-k-1 >= m){
            cout << 0 << "\n";
    }
    else{
            ll total = (((fact[n+m]*factinv[n])%MOD)*factinv[m])%MOD;
            //cout << total << "\n";
            if(n == k){
                    cout << total << "\n";
            }
            else{
                    ll bad = (((fact[n+m]*factinv[n-k-1])%MOD)*factinv[m+k+1])%MOD;
                    ll ans = total - bad;
                    if(ans < 0) ans += MOD;
                    cout << ans << "\n";
            }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    //ll t;
    //cin >> t;
    t = 1;
    while(t--)solve();
    return 0;
}