题目描述

作为帕鲁王国的国王，Nathanwong 深知直升机飞行控制系统的重要性。因此，发展帕鲁王国的计算机产业刻不容缓。遗憾的是，帕鲁尚未掌握微电子的制造工艺，Nathanwong 只好调动 $n$ 只帕鲁模拟计算机电路。这些帕鲁被依次编号为 $1,2,\dots, n$。

具体来说，每一只帕鲁将在该电路中，扮演逻辑门和输入引脚的功能：

• 与门。扮演与门的帕鲁，将从 一些 帕鲁那里接受运算结果，并将它所接受的全部数据进行逻辑与运算后，作为运算结果传递出去。
• 或门。扮演或门的帕鲁，将从 一些 帕鲁那里接受运算结果，并将它所接受的全部数据进行逻辑或运算后，作为运算结果传递出去。
• 非门。扮演非门的帕鲁，将从 一个 帕鲁那里接受运算结果，并将它接受的唯一数据进行逻辑非运算后，作为运算结果传递出去。
• 输入引脚。扮演输入引脚的帕鲁，将直接从Nathanwong 处接受数据，并直接作为运算结果传递出去。

每一只帕鲁，只能进行布尔运算。也就是说，它们只会处理数据 $0$ 和 $1$。扮演输入引脚的帕鲁，从Nathanwong 处也只会接受到数据 $0$ 和 $1$。Nathanwong 深知帕鲁王国等级森严，因此，编号为 $i$ 的帕鲁，若扮演的是逻辑门，只会从编号大于 $i$ 的帕鲁处接受数据。编号为 $1$ 的帕鲁一定扮演逻辑门，其运算结果直接报告至 Nathanwong。

Nathanwong 想要知道，存在多少种不同的输入方式，使得 $1$ 号帕鲁报告的运算结果为 $k$？两种输入方式不同，当且仅当有一只或以上扮演输入引脚的帕鲁，从Nathanwong 处接受的输入数据不同。

由于答案可能很大，你只需要输出答案对 $998,244,353$ 取模的结果。

输入格式

从文件 king.in 中读入数据。

第一行为两个整数 $n,k$。

接下来 $n$ 行，第 $i$ 行描述第 $i$ 个帕鲁。

每行先输入一个字符串 $r_i$，and、or、not、input 依次表示第 $i$ 个帕鲁扮演与门、或门、非门、输入引脚。

若第 $i$ 个帕鲁扮演逻辑门，则再输入一个整数 $x_i$，表示该帕鲁共从 $x_i$ 个帕鲁处接受数据。接下来 $x_i$ 个整数，每个整数为一个帕鲁的编号。保证当第 $i$ 个帕鲁扮演的是非门时，$x_i = 1$。

若第 $i$ 个帕鲁扮演输入引脚，则该行无其他输入。

输出格式

输出到文件 king.out 中。

输出一行一个整数，表示答案对 $998,244,353$ 取模的结果。

7 0
or 2 2 3
and 2 6 7
and 2 4 5
input
input
input
input

9

样例 $1$ 解释

上图是帕鲁模拟的数字电路图。

见下方附加文件压缩包内 king/king2.in

见下方附加文件压缩包内 king/king2.out

样例 $2$ 解释

样例 $2$ 满足 测试点 $14 \sim 16$ 的限制。

见下方附加文件压缩包内 king/king3.in

见下方附加文件压缩包内 king/king3.out

样例 $3$ 解释

样例 $3$ 满足 测试点 $17 \sim 19$ 的限制。

见下方附加文件压缩包内 king/king4.in

见下方附加文件压缩包内 king/king4.out

数据范围

对于 $100\%$ 的测试数据，保证 $1 \leq n \leq 10^5$，$k \in \{0, 1\}$，字符串 $r_i$ 为 and、or、not、input 中的一个。保证扮演逻辑门的帕鲁只会从编号大于自己的帕鲁处接受数据。保证除 $1$ 号帕鲁外，每一只帕鲁向且仅向一只帕鲁传递运算结果。

测试点编号	$n =$	特殊性质
$1 \sim 7$	$12$	无
$8 \sim 13$	$5000$
$14 \sim 16$	$10^5$	$\text{A}$
$17 \sim 19$		$\text{B}$
$20 \sim 25$		无

特殊性质 $\text{A}$ : 没有扮演与门的帕鲁。

特殊性质 $\text{B}$ : 没有扮演或门的帕鲁。

附加文件

king