#include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <iostream>

 #include <vector>

 using namespace std;

 typedef long long LL;

 typedef vector<vector<int> > Mat;

 const int MAXV = ;

 const int MAXE = MAXV * MAXV;

 const int MOD = 1e9 + ;

 void debug(const Mat &a) {

     puts("#debug:");

     for(auto &i : a) {

         for(auto j : i) printf("%d ", j);

         puts("");

     }

 }

 int inv(int x) {

     if(x == ) return ;

     return LL(MOD - MOD / x) * inv(MOD % x) % MOD;

 }

 int det(Mat &a, int n) {

     LL res = ;

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

         if(a[i][i] == ) return ;

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

             LL t = LL(a[j][i]) * inv(a[i][i]) % MOD;

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

                 a[j][k] -= (a[i][k] * t) % MOD;

                 if(a[j][k] < ) a[j][k] += MOD;

             }

         }

         res = (res * a[i][i]) % MOD;

     }

     return res;

 }

 void guass(Mat &a, int n) {

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

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

             LL t = LL(a[j][i]) * inv(a[i][i]) % MOD;

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

                 a[j][k] -= (a[i][k] * t) % MOD;

                 if(a[j][k] < ) a[j][k] += MOD;

             }

         }

     }

     for(int i = n - ; i >= ; --i) {

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

             a[i][n] -= (LL(a[i][j]) * a[j][n]) % MOD;

             if(a[i][n] < ) a[i][n] += MOD;

         }

         a[i][n] = LL(a[i][n]) * inv(a[i][i]) % MOD;

     }

 }

 int la[MAXE], lb[MAXE], kind[MAXE];

 int T, n, m, k;

 int get_column(int a) {

     Mat mat(n, vector<int>(n));

     for(int i = ; i < m; ++i) {

         int t = (kind[i] & ) * a + (kind[i] >> );

         mat[la[i]][la[i]] += t;

         mat[lb[i]][lb[i]] += t;

         mat[la[i]][lb[i]] = mat[lb[i]][la[i]] = (t >  ? MOD - t : );

     }

     return det(mat, n);

 }

 int solve() {

     Mat mat(n, vector<int>(n + ));

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

         LL tmp = ;

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

             mat[i][j] = tmp, tmp = (tmp * i) % MOD;

         mat[i][n] = get_column(i);

     }

     //debug(mat);

     guass(mat, n);

     int res = ;

     for(int i = ; i <= k; ++i) {

         res += mat[i][n];

         if(res >= MOD) res -= MOD;

     }

     return res;

 }

 int main() {

     scanf("%d", &T);

     for(int t = ; t <= T; ++t) {

         scanf("%d%d%d", &n, &m, &k);

         for(int i = ; i < m; ++i) {

             scanf("%d%d%d", &la[i], &lb[i], &kind[i]);

             la[i]--, lb[i]--;

         }

         printf("Case #%d: %d\n", t, solve());

     }

 }