题目背景

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

题目描述

集训从 $\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 表示女生，其余为男生）。

输出格式

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

5 3
b 3 5 7
g 2 8 5
b 6 10 2
g 4 1 9
g 8 10 3

20

见 ex_terrorists2.in/ans
这个样例满足 sub2 的约束条件

见 ex_terrorists3.in/ans
这个样例满足 sub3 的约束条件

提示

数据范围

本题使用捆绑测试。

$\text{sid}$	$pts$	$N$	$m$	特殊性质
$1$	$20$	$\leq 10^5$	$\leq 8$	无
$2$	$30$	$\leq 10^6$	$\leq 50$	有
$3$	$50$		$\leq 100$	无

特殊性质：保证数据在一定范围内随机生成。

对全部的数据，$1 \leq t,c,l \leq 10^9, 1 \leq N \leq 10^6, 1 \leq m \leq 100$。