Team Formation with Mentor Constraints

In this season of 'Good Coder', elite students from n different schools across c cities participate. Each school i belongs to city \(b_i\) and has \(s_i\) participants.

The mentor selection stage is governed by the following additional rules:

• All participants from the same city must join the same camp (i.e. choose a mentor from the same team).
• All participants from the same school must choose the same mentor.

Furthermore, exactly \(k\) schools have students who dislike one specific mentor. For a school with a dislike, all of its students will refuse to join that mentor's team.

Assume that there are exactly two mentors available, one from each camp (mentor 1 and mentor 2). For each city the following rule applies: if any school in that city has a dislike against a mentor, then that mentor's team is not available for all schools in that city. Otherwise, both teams are available.

Your task is to count the number of valid overall team formations. A formation is defined by the assignment of a mentor to every school. Two formations are considered different if and only if there exists at least one school whose assigned mentor differs between the two formations.

Since the answer might be very large, output it modulo \(998244353\).

inputFormat

The first line contains three integers: \(c\), \(n\), and \(k\), representing the number of cities, the number of schools, and the number of schools with a mentor dislike, respectively.

Each of the following \(n\) lines contains three integers: \(b\), \(s\), and \(d\). Here:

• \(b\) (\(1 \le b \le c\)) is the city number the school belongs to.
• \(s\) is the number of participants from that school (this value does not affect the count).
• \(d\) indicates the disliked mentor. If \(d = 0\), the school has no mentor preference; if \(d = 1\) or \(d = 2\), the school dislikes mentor 1 or mentor 2, respectively. It is guaranteed that exactly \(k\) schools have \(d \neq 0\).

outputFormat

Output a single integer: the number of valid team formations modulo \(998244353\).

sample

2 3 1
1 50 1
1 60 0
2 40 0

2