不得不说,dp和dp之间差距不是一点点...
都快自闭了啊,虽然自闭不是一天两天了..这题还好吧...emmm,上个dp是真的恶心..
我不知道为什么,口上几分钟的东西,代码1h甚至还久...这****啊
代码如下:

/*
cnm
byw
NO BUG
cao!
***!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+10,M=15;
const ll mod=987654321;
ll f[N][M];//到了第i个,颜色是j的可行方案数
vector<ll>b[N];
ll a[N];
ll ck[N];
int main()
{
    int n,m,c;
    cin>>n>>m>>c;
    while(m--)
    {
        int x1,x2,x3;
        cin>>x1>>x2>>x3;
        if(x1==1)
        {
            if(a[x2]&&a[x2]!=x3)
            {
                puts("0");
                return 0;
            }
            a[x2]=x3;
        }
        else if(x1==2)
        {
            if(a[x2]==x3)
            {
                puts("0");
                return 0;
            }
            b[x2].push_back(x3);
        }
        else    ck[max(x2,x3)]=1;
    }
    ll sum=0,ans=0;
    for(int i=(a[1]?a[1]:1);i<=(a[1]?a[1]:c);i++)//枚举第一个的颜色.
    {
        if(find(b[1].begin(),b[1].end(),i)!=b[1].end()) continue;
        memset(f,0,sizeof f);
        f[1][i]=1;
        sum=1;
        for(int j=2;j<=n;j++)//然后就是一个一个dp吧.
        {
            if(ck[j])//假如要求和前面相同的相同.
            {
                for(int k=1;k<=c;k++) f[j][k]=f[j-1][k];
                if(a[j])
                {
                    for(int k=1;k<=c;k++)
                        if(a[j]!=k) f[j][k]=0;
                }
                for(int k=0;k<b[j].size();k++) f[j][b[j][k]]=0;
                sum=0;
                for(int k=1;k<=c;k++)
                    sum=(sum+f[j][k])%mod;
                continue;
            }
            for(int k=(a[j]?a[j]:1);k<=(a[j]?a[j]:c);k++)
            {
                if(find(b[j].begin(),b[j].end(),k)!=b[j].end()) continue;
                f[j][k]=(f[j][k]+sum-f[j-1][k]+mod)%mod;
            }
            sum=0;
            for(int k=(a[j]?a[j]:1);k<=(a[j]?a[j]:c);k++)
            {
                if(find(b[j].begin(),b[j].end(),k)!=b[j].end()) continue;
                sum=(sum+f[j][k])%mod;
            }
        }
        for(int k=1;k<=c;k++)  if(k!=i) ans=(f[n][k]+ans)%mod;
    }
    cout<<ans<<'\n';
    return 0;
}