#include<bits/stdc++.h>
using db = double;
using std::cin;
using std::cout;
using cp = std::complex<db>;
using ll = long long;
using pi = std :: pair <int, int> ; 
using u64 = unsigned long long;
const int mod = 1e6 + 3; 
const int N = 1000005;

bool cmn(int & x, int y) {
    if(x > y) return x = y, 1;
    return 0; 
}
int n, L;
pi dp[4][105][4], way[4][4];
int e[20];


pi operator + (pi a, int b) {
    return {a.first + b, a.second};
}
pi operator * (const pi & a, const pi & b) {
	return {a.first + b.first, (u64) a.second * b.second % mod };
}
void add(int & x, int y) {
	if((x += y) >= mod) {
		x -= mod;
	}
}
pi& operator += (pi & a, const pi & b) {
	if(b.first > a.first) {
		return a = b;
	} else if(b.first == a.first) {
		return add(a.second, b.second), a;
	} else {
		return a;
	}
}
void trans(pi & a, pi b) {
    if(b.first > a.first) {
        a = b;
    }
    else if(b.first == a.first) {
        a.second = (a.second + b.second) % mod; 
    }
}

int count(int S) {
    if (S==63) return 3;
    while (S&1) S|=1<<6,S>>=1;
    int res=0;
    while (S) {
        while (!(S&1)) S>>=1;
        int c=0;
        while (S&1) S>>=1,++c;
        if (c&1) return -1;
        res+=c/2;
    }
    return res;
}

void work(int S, pi dp[105][4]) {
    for(int i = 0; i <= L; i++)
    for(int j = 0; j < 4; j++) dp[i][j] = {-100, 0};
    dp[0][S] = {0, 1};
	if(!S) dp[0][3] = {1, 1};

	// cout << count(62) << ' ' << count(15) << ' ' << count(30) << '\n';

    for(int i = 1; i <= L; i++) {
        for(int a = 0; a < 4; a++) {
            for(int x = 0; x < 64; x++) {
                int c = count(x); 
				if(x % 4 == 3) {
					int t = count(x ^ 3);
					if(x == 63 || t == -1 || t + 1 != c) {
						
					} else {
						continue;
					}
				}
                if((x & a) == 0 && c != -1) {

                    trans(dp[i][(x >> 4 & 1) | ((x >> 3 & 1) << 1)], dp[i - 1][a] * pi(c, 1));
					// cout << "Trans ------- " << i- 1 <<' ' << a << ' ' << x << ' ' << c << '\n';
                }
            }
        }
	//	for(int a= 0; a < 4; a++) cout << dp[i][a].first <<' ';cout<<'\n';
	//	for(int a= 0; a < 4; a++) cout << dp[i][a].second <<' ';cout<<'\n';
    }
    for(int T = 0; T < 4; T++) 
    for(int o = 0; o < 4; o++) 
    if((o & T) == 0) trans(way[S][T], dp[L][o]);
}

int cut(int S) {
    int c = 0; 
    for(int i = 0; i < n; i++) {
        if(!(S >> i & 1)) c += __builtin_popcount(S & e[i]); 
        // cout << i << ' ' << e[i] << '\n';
    }
    return c; 
}

std :: vector <int> getseq() {
    std :: vector <int> dp(1 << n, 1e9), tr(1 << n);
    for(int i = 0; i < n; i++) dp[1 << i] = 0, tr[1 << i] = i;
    for(int S = 1; S < (1 << n); S++) {
        dp[S] = std :: max(dp[S], cut(S));
        // cout << S << ' ' << dp[S] << '\n';
        for(int i = 0; i < n; i++)
        if(!(S >> i & 1)) {
            int T = S | (1 << i);
            if(cmn(dp[T], dp[S]))
                dp[T] = dp[S], tr[T] = i; 
        }
    }
    std :: vector <int> seq; 
    int cur = (1 << n) - 1; 
    while(cur) {
        int x = tr[cur];
        seq.push_back(x);
        cur ^= 1 << x; 
    }
    reverse(seq.begin(), seq.end());
    // cout << dp[(1 << n) - 1] << '\n';
    return seq; 
}

pi get(int a, int b, int c, int d) {
    return way[d + c * 2][a + b * 2];
}

std::array<int, 3> edge[N];

std::array<std::pair<int, int>, 3> edge_id[N];

int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> L; 

    for(int S = 0; S < 4; S++) work(S, dp[S]);
/*
	for(int a : {0, 1})
		for(int b : {0, 1})
			for(int c : {0, 1})
				for(int d : {0, 1})
					assert(get(a, b, c, d) == get(d, c, b, a));
	cout << get(0, 0, 0, 0).first << '\n';
	cout << get(0, 0, 0, 0).second << '\n';
	//return 0;
	*/
    for(int i = 0; i < n; i++) {
        int a, b, c; 
        cin >> a >> b >> c; 
		edge[i][0] = a - 1;
		edge[i][1] = b - 1;
		edge[i][2] = c - 1;
        e[i] |= 1 << (a - 1);
        e[i] |= 1 << (b - 1);
        e[i] |= 1 << (c - 1);
    }
	for(int i = 0;i < n;++i) {
		for(int x = 0;x < 3;++x) {
			int t = edge[i][x];
			int y = std::find(edge[t].begin(), edge[t].end(), i) - edge[t].begin();
			assert(y != 3);
			edge_id[i][x] = {t * 6 + y * 2, t * 6 + y * 2 + 1};
		}
	}
    std :: vector <int> seq = getseq();


	std::vector<int> states;
	for(int i = 0;i < 1 << 6;++i) {
		int cnt[6] = {};
		for(int j = 0;j < 6;++j) if(i >> j & 1) {
			cnt[j] += 1;
			cnt[(j + 1) % 6] += 1;
		}
		int bad = 0, s = 0;
		for(int j = 0;j < 6;j += 2) if(i >> j & 1) {
			bad = 1;
		}
		for(int j = 0;j < 6;++j) {
			if(cnt[j] >= 2) {
				bad = 1;
			}
			if(cnt[j] > 0) {
				s |= 1 << j;
			}
		}
		if(!bad) states.emplace_back(s);
	}

	int S = 0, T = (1 << n) - 1;
	std::vector<pi> dp(1, {0, 1});
	std::vector<int> in(n, 1);
	std::vector<int> index(6 * n, -1), cuts;
	for(int i = 0;i < n;++i) {
		std::vector<int> new_index(6 * n, -1), new_cuts;
		int cut_size = 0;
		int x = seq[i];
		S ^= 1 << x;
		T ^= 1 << x;
		in[x] = 0;
		for(int i = 0;i < n;++i) if(S >> i & 1) {
			cut_size += __builtin_popcount(e[i] & T);
		}
		int cnt = 0;
		for(int i = 0;i < n;++i) if(T >> i & 1) {
			for(int j = 0;j < 3;++j) {
				int go = edge[i][j];
				if(S >> go & 1) {
					new_index[edge_id[i][j].first] = cnt++;
					new_index[edge_id[i][j].second] = cnt++;
					new_cuts.push_back(edge_id[i][j].first);
					new_cuts.push_back(edge_id[i][j].second);
				}
			}
		}
		std::vector<pi> g(1 << (cut_size * 2), {-100, 1});
		assert(cut_size * 2 == new_cuts.size());
		assert(dp.size() == 1 << cuts.size());

		for(int i = 0;i < (int) dp.size();++i) if(dp[i].first >= 0) {
			for(int s : states) {
				pi z(__builtin_popcount(s) / 2, 1);
				for(int j = 0;j < 3;++j) {
					int go = edge[x][j];
					if(S >> go & 1) {
						auto [a, b] = edge_id[x][j];
						assert(index[a] >= 0);
						assert(index[b] >= 0);
						z = z * get(s >> (j * 2) & 1, s >> (j * 2 + 1) & 1, i >> index[a] & 1, i >> index[b] & 1); // TODO
					}
				}
				int new_s = 0;
				for(int x = 0;x < (int) cuts.size();++x) {
					if((i >> x & 1) && new_index[cuts[x]] >= 0) {
						// asseert(new_index[cuts[x]] >= 0);
						new_s |= 1 << new_index[cuts[x]];
					}
				}
				for(int j = 0;j < 6;++j) if(new_index[j + x * 6] >= 0 && (s >> j & 1)) {
					new_s |= 1 << new_index[j + x * 6];
				}
				g[new_s] += dp[i] * z;
			}
		}
		dp = g;
		index = new_index;
		cuts = new_cuts;
	}
//	cout << dp[0].first << '\n';
	cout << dp[0].second << '\n';
	return 0; 

}