#include #define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i)) #define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i)) #define rep(i, n) For((i), 0, (n)) #define rrep(i, n) rFor((i), (n), 0) #define fi first #define se second using namespace std; typedef long long lint; typedef unsigned long long ulint; typedef pair pii; typedef pair pll; template bool chmax(T &a, const T &b){if(a bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;} template T div_floor(T a, T b){ if(b < 0) a *= -1, b *= -1; return a>=0 ? a/b : (a+1)/b-1; } template T div_ceil(T a, T b){ if(b < 0) a *= -1, b *= -1; return a>0 ? (a-1)/b+1 : a/b; } constexpr lint mod = 1e9+7; constexpr lint INF = mod * mod; constexpr int MAX = 200010; template struct modint{ using i64=int_fast64_t; i64 a; modint(const i64 a_=0): a(a_){ if(a>MOD) a%=MOD; else if(a<0) (a%=MOD)+=MOD; } modint inv(){ i64 t=1, n=MOD-2, x=a; while(n){ if(n&1) (t*=x)%=MOD; (x*=x)%=MOD; n>>=1; } modint ret(t); return ret; } bool operator==(const modint x) const{return a==x.a;} bool operator!=(const modint x) const{return a!=x.a;} modint operator+(const modint x) const{ return modint(*this)+=x; } modint operator-(const modint x) const{ return modint(*this)-=x; } modint operator*(const modint x) const{ return modint(*this)*=x; } modint operator/(const modint x) const{ return modint(*this)/=x; } modint operator^(const lint x) const{ return modint(*this)^=x; } modint &operator+=(const modint &x){ a+=x.a; if(a>=MOD) a-=MOD; return *this; } modint &operator-=(const modint &x){ a-=x.a; if(a<0) a+=MOD; return *this; } modint &operator*=(const modint &x){ (a*=x.a)%=MOD; return *this; } modint &operator/=(modint x){ (a*=x.inv().a)%=MOD; return *this; } modint &operator^=(lint n){ i64 ret=1; while(n){ if(n&1) (ret*=a)%=MOD; (a*=a)%=MOD; n>>=1; } a=ret; return *this; } modint operator-() const{ return modint(0)-*this; } modint &operator++(){ return *this+=1; } modint &operator--(){ return *this-=1; } bool operator<(const modint x) const{ return a; vector fact; vector revfact; void setfact(int n){ fact.resize(n+1); revfact.resize(n+1); fact[0] = 1; rep(i, n) fact[i+1] = fact[i] * mint(i+1); revfact[n] = fact[n].inv(); for(int i=n-1; i>=0; i--) revfact[i] = revfact[i+1] * mint(i+1); } mint getC(int n, int r){ if(n>; using mat = array, 216>; mat c; void mul(mat a, mat b){ int n = 216; rep(i, n)rep(j, n){ c[i][j] = 0; rep(k, n) c[i][j] += a[i][k] * b[k][j]; } } mat pow(mat a, int n){ int m = 216; mat b; rep(i, m)rep(j, m) b[i][j] = (i == j); while(n){ if(n & 1) mul(a, b), swap(b, c), --n; else mul(a, a), swap(a, c), n >>= 1; } return b; } int main(){ int K, m; lint n; scanf("%d%d%lld", &K, &m, &n); int p[m], q[m], r[m]; rep(i, m){ scanf("%d%d%d", &p[i], &q[i], &r[i]); --p[i]; --q[i]; --r[i]; } if(n == 3){ set> S; rep(i, m)if(p[i]==0 && r[i]==0) S.insert({p[i], {q[i], r[i]}}); printf("%d\n", S.size()); return 0; } mat a; rep(i, 216)rep(j, 216) a[i][j] = 0; int idx[6][6][6], cur = 0; rep(i, 6)rep(j, 6)rep(k, 6) idx[i][j][k] = cur++; rep(i, m)rep(j, m)if(q[i]==p[j] && r[i]==q[j]){ a[idx[p[i]][q[i]][r[i]]][idx[p[j]][q[j]][r[j]]] = 1; } a = pow(a, n-3); mint ans = 0; rep(j, K)rep(k, K)rep(s, K)rep(t, K) ans += a[idx[0][j][k]][idx[s][t][0]]; printf("%lld\n", ans.a); }