该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

目标逻辑值

题目描述

有 $N+1$ 个布尔变量 $x_0,x_1,\ldots,x_N$。每个变量都可以独立取 0 或 1，其中 0 表示假，1 表示真。

先令表达式的值为 $x_0$。随后依次执行 $N$ 次运算：第 $i$ 次把当前值与 $x_i$ 通过给定的 AND 或 OR 运算合并。

给定目标值 $T$，求有多少种 $(x_0,x_1,\ldots,x_N)$ 的赋值方案，使最终表达式的值等于 $T$。

输入格式

第一行输入两个整数 $N,T$。

• $1\le N\le 60$
• $T\in\{0,1\}$

接下来 $N$ 行，第 $i$ 行输入一个字符串 $S_i$，保证 $S_i$ 为 AND 或 OR。

输出格式

输出使最终表达式值等于 $T$ 的赋值方案数。

输入输出样例 #1

输入 #1

1 0
AND

输出 #1

3

输入输出样例 #2

输入 #2

2 1
OR
AND

输出 #2

3

说明/提示

样例 1 中，只有 $(x_0,x_1)=(1,1)$ 的结果为 1，其余三种赋值的结果均为 0。

样例 2 的表达式为 $(x_0\mathbin{\mathrm{OR}}x_1)\mathbin{\mathrm{AND}}x_2$。当 $x_2=1$ 且 $x_0,x_1$ 不全为 0 时结果为 1，共有三种方案。