RT

#include<bits/stdc++.h>
using namespace std;
typedef long long lwl;

const int N = 5e4 + 5, inf = 0x3f3f3f3f;
const int mod = 987654321;

struct node{
	int type,x,p;
}q[1005];

int n,m,c;
int col[N];
int flag[N][15];
lwl dp[N][15];
int id[N];
int h[N];

lwl fr(){
	lwl x = 0, flag = 1;
	char t;
	t = getchar();
	while (t < 48 || t > 57){
		if (t == '-') flag = -1;
		t = getchar();
	}
	while (t >= 48 && t <= 57){
		x = x * 10 + t - 48;
		t = getchar();
	}
	return x*flag;
}

void fw(lwl x){
	if (x < 0) putchar('-'),x = -x;
	if (x > 9){
		fw(x / 10);
	}
	putchar(x % 10 + '0');
	return ;
}

int min(int a,int b){
	if (a > b) return b;
	return a;
}

int max(int a,int b){
	if (a < b) return b;
	return a;
}

int find(int x){
	if (x != h[x]) h[x] = find(h[x]);
	return h[x];
}

int main(){
	n = fr(),m = fr(),c = fr();
	for (int i = 1; i <= n; i ++) {
		h[i] = i;
	}
	int type,x,p;
	int cnt = 0;
	while (m --) {
		type = fr(),x = fr(),p = fr();
		if (type == 3) {
			h[find(x)] = h[find(p)];
		}
		else q[++ cnt] = {type,x,p};
	}
	cnt = 0;
	for (int i = 1; i <= n; i ++) {
		if (h[i] != i) continue;
		id[i] = ++ cnt;
		for (int j = 1; j <= c; j ++) {
			flag[cnt][j] = 1;
		}
	}
	for (int i = 1; i <= cnt; i ++) {
		type = q[i].type,x = q[i].x,p = q[i].p;
		if (type == 1) {
			for (int j = 1; j <= c; j ++) {
				if (j == p) continue;
				flag[id[find(x)]][j] = 0;
			}
		}
		else flag[id[find(x)]][p] = 0;
	}
	lwl ans = 0;
	for (int t = 1; t <= c; t ++) {
		if (! flag[id[find(1)]]) continue;
		memset(dp,0,sizeof dp);
		dp[1][t] = 1;
		for (int tt = 2; tt <= cnt; tt ++) {
			for (int j = 1; j <= c; j ++) {
				if (!flag[tt][j]) continue; 
				for (int k = 1; k <= c; k ++) {
					if (k == j) continue;
					dp[tt][j] = (dp[tt][j] + dp[tt - 1][k]) % mod;
				}
			}
		}
		for (int j = 1; j <= c; j ++) {
			if (j == t) continue;
			ans = (ans + dp[cnt][j]) % mod;
		}
	}
	fw(ans);
	return 0;
}