P15250 [NOSOI R1] Terrorists

> 不幸的是，我们有天下最勤奋的领导。

集训从 $\mathrm{Day}\ 0$ 开始，到 $\mathrm{Day}\ N$ 结束，共 $N+1$ 天。 机房中共有 $m$ 名选手，每位选手有四个属性： * 游戏时长 $t$； * 校服整齐度 $c$； * 头发长度 $l$； * 性别 $g \in \{\text{boy}, \text{girl}\}$。 每一天都有领导前来检查一名选手，领导满意与否取决于相邻两天被检查选手的表现。领导在第 $i$ 天（$i \ge 1$）满意当且仅当**同时满足**： * $t_i \le t_{i-1}$； * $c_i \ge c_{i-1}$； * $l_i \le l_{i-1}$ 或 $g_i = \text{girl}$。 特别地，在第 $0$ 天，领导总是满意。 由于领导只会比较当前天与前一天的情况，而不会记住更早的信息，因此只需保证相邻两天的被检查选手满足上述关系即可。 小 $Y$ 想知道，有多少种不同的检查序列（即一个长度为 $N+1$ 的数组 $(a_0, a_1, \dots, a_N)$，其中 $a_k$ 表示第 $k$ 天被检查的选手编号），能够使得领导在每一天都满意。 由于答案可能很大，请输出其对 $998244343$ 取模的结果。

输入共 $m+1$ 行。 一行两个整数 $m,N$，表示机房人数和集训天数； 接下来 $m$ 行，每行 $1$ 个字符 $g_i$ 和 $3$ 个整数 $t_i,c_i,l_i$。 分别表示性别，游戏时长、校服整齐度、头发长度 （$g_i$ 为字符 `g` 表示女生，其余为男生）。

输出一行一个整数，表示答案取模之后的结果。

#### 数据范围 本题使用捆绑测试。 |$\text{sid}$|$pts$|$N$|$m$|特殊性质| |:--:|--|--|--|--| |$1$|$20$|$\leq 10^5$|$\leq 8$|无| |$2$|$30$|$\leq 10^6$|$ \leq 50$|有| |$3$|$50$|$\leq 10^6$|$\leq 100$|无| 特殊性质：保证数据在一定范围内随机生成。 对全部的数据，$1 \leq t,c,l \leq 10^9, 1 \leq N \leq 10^6, 1 \leq m \leq 100$。