题目描述

小明负责管理社区花园里的 $N$ 个花盆，每个花盆里可以种两种不同的花：A 型（红色）或 B 型（蓝色）。最近，社区的 $M$ 位居民提出了种植要求，希望小明按照他们的喜好来安排花盆的花色。

每位居民的要求分为两种：

• S x y：花盆 $x$ 和花盆 $y$ 必须种同一种花（都为 A 或都为 B）。
• D x y：花盆 $x$ 和花盆 $y$ 必须种不同的花（一个 A，另一个 B）。

小明需要计算，满足所有居民要求的种植方案一共有多少种。由于结果可能很大，最终答案需要用二进制表示（例如，方案数为 $2$ 时输出 10，方案数为 $0$ 时输出 0）。

输入格式

• 第一行：两个整数 $N$（花盆数量）和 $M$（居民要求数量）。
• 接下来 $M$ 行：每行一个字符 S 或 D，后跟两个整数 $x, y$，表示一位居民的要求。

输出格式

一行二进制数，表示满足所有要求的种植方案数。如果没有任何方案符合条件，输出 0。

输入输出样例

样例输入 1

3 2  
S 1 2  
D 3 2  

样例输出 1

10  

样例解释 1

• 花盆 1 和 2 必须同色，花盆 3 和 2 必须异色。
• 可能的方案有两种：
  1. 花盆 1 和 2 种 A，花盆 3 种 B；
  2. 花盆 1 和 2 种 B，花盆 3 种 A。
• 方案数为 $2$，二进制表示为 10。

说明/提示

对于 $20\%$ 的数据：$2 \leq N \leq 10$。

对于 $100\%$ 的数据：$2 \leq N \leq 10^5$，$1 \leq M \leq 10^5$，$1 \leq x, y \leq N$。