U140360 购物清单

光阴似箭，日月如梭。不知不觉间，时间已经快进到$Seaway$带着一家老~~婆~~小~~孩~~过上了幸福快乐的生活......

当然，虽然生活的大体格调是幸福而快乐的，但是$Seaway$依然躲不过生活中的柴米油盐酱醋茶等琐碎小事。其中，最让他为难的便是半个月一次的采购了...... 每次采购，$Seaway$要列出一份购物清单，并**按清单顺序**购入下半个月所需要的$n$件物品。超市一共有$2^k$种物品。为了方便，$Seaway$把这些物品从$0-2^k-1$编号。现在问题在于，$Seaway$每次采购都要满足老婆孩子的$m$条要求，这些要求形如$(l,r,x)$。其意义是：假设$Seaway$的购物清单是一个数列$a$，那么对于第$i$条要求$(l_i,r_i,x_i)$，$Seaway$的购物清单必须满足：$a[l_i] \&a[l_i+1]\&\cdots\&a[r_i]=x_i$。其中$\&$是按位与运算。$Seaway$的购物清单合法，当且仅当它能同时满足老婆孩子的$m$条要求。 $Seaway$在经过严密地思考后发现，这样的清单不唯一。所以他想请你帮他统计：对于这$m$条要求，有多少种清单合法。我们定义两个清单$a,b$不同，当且仅当存在至少一个位置$i$使得$a_i\neq b_i$。答案对$998,244,353$取模。

从文件$list.in$中读入数据。 第一行三个整数$n,m,k$，意义如题目描述所示。 接下来的$m$行，每行三个整数$l_i,r_i,x_i$，描述一个限制$(l,r,x)$。

输出到文件$list.out$中。 输出一行一个整数$ans$，表示满足条件的清单种数按要求取模后的结果。

【**样例1解释**】 符合要求的清单有以下三种： $[3,3,7,6],[3,7,7,6],[7,3,7,6]$。 【**数据范围**】 对于$10\%$的数据，$1\le n,m\le 9,1\le k\le 3$。 对于$40\%$的数据，$1\le n,m\le 100,1\le k\le 6$。 对于$80\%$的数据，$1\le n,m\le 10^5，1\le k\le 30$。 对于$90\%$的数据，$1\le n,m\le 2\times 10^5,1\le k\le 63$。 对于全部数据，$1\le n,m\le 5\times 10^5,1\le k\le 64$。