#include "bits/stdc++.h" using namespace std; #define int long long #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--) #define REP(i, n) for(int i=0; i<(n); i++) #define RREP(i, n) for(int i=(n-1); i>=0; i--) #define REP1(i, n) for(int i=1; i<=(n); i++) #define RREP1(i, n) for(int i=(n); i>=1; i--) #define ALL(a) (a).begin(),(a).end() #define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end()); #define CONTAIN(a, b) find(ALL(a), (b)) != (a).end() #define out(...) printf(__VA_ARGS__) #if DEBUG #define debug(...) printf(__VA_ARGS__) #else #define debug(...) /* ... */ #endif templatebool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b struct ModInt { static const int Mod = MOD; unsigned x; ModInt() : x(0) { } ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; } ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; } int get() const { return (int)x; } ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; } ModInt &operator/=(ModInt that) { return *this *= that.inverse(); } ModInt operator+(ModInt that) const { return ModInt(*this) += that; } ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } return ModInt(u); } bool operator==(ModInt that) const { return x == that.x; } bool operator!=(ModInt that) const { return x != that.x; } ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; } }; template ostream& operator<<(ostream& st, const ModInt a) { st << a.get(); return st; }; template ModInt operator^(ModInt a, unsigned long long k) { ModInt r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; } typedef ModInt<1000000007> mint; int N,M,K; int A[SIZE]; // i番目,3つ前,2つ前,1つ前→組み合わせ数 int DP[2][6][6][6]; struct Tup { int a,b,c; }; // 3*(2^i)番目,前のTupのindex,次のTupのindex→組み合わせ数 mint DP2[62][SIZE][SIZE]; int MOD=1e9+7; int E[6][6][6]; void solve() { cin>>K>>M>>N; int p,q,r; vector tups; vector s0; REP(i,M) { cin>>p>>q>>r; --p;--q;--r; if (!p) s0.push_back(tups.size()); tups.push_back({p,q,r}); E[p][q][r]=1; } int size = tups.size(); REP(i,size)REP(j,size) { auto [a,b,c] = tups[i]; auto [d,e,f] = tups[j]; if (E[b][c][d] && E[c][d][e]) { DP2[0][i][j] += 1; } } N -= 3; int T = N/3; // i番目,-3,-2,-1 vector ans(size), tmp(size); for (int i:s0) { ans[i] = 1; } REP(i,61) { REP(j,size)REP(k,size)REP(l,size) { DP2[i+1][j][l] += DP2[i][j][k]*DP2[i][k][l]; } if (T & (1LL<