### 问题描述 小齐的农场有 $N$ 片牧场，由于长时间的干旱，草都枯萎了。然而，雨季即将到来，是时候进行"复绿"了。小齐的仓库里有两个桶，每个桶里有一种不同类型的草籽。他想在每个牧场里种植草，每片牧场选择一种类型的草。 作为一名奶牛养殖者，小齐希望确保满足他的 $M$ 头奶牛的特殊饮食需求。每头奶牛有两片最喜欢的牧场。有一些奶牛有饮食限制，它们只能在它们两个最喜欢的牧场中种植相同类型的草。对于这样的奶牛，小齐当然希望确保这两片牧场中有相同类型的草。而其他奶牛有截然不同的饮食要求，它们需要在两片不同的草地中种植不同类型的草。 请帮助小齐确定他可以在 $N$ 片牧场中种植草的不同方法数。 ### 输入格式 第一行包含两个整数 $N$ 和 $M$。接下来的 $M$ 行，每行包含一个字符，可能是 $S$ 或 $D$，后跟两个整数，范围在 $1 \sim N$，描述一头奶牛的两个最喜欢的牧场。如果字符是 $S$，表示这行代表一头需要在其两个最喜欢的牧场中种植相同类型草的奶牛。如果字符是 $D$，表示这行代表一头需要在其两个最喜欢的牧场中种植不同类型草的奶牛。 ### 输出格式 输出小齐在 $N$ 片牧场中种植草的不同方法数。请以二进制形式表示你的答案。 ### 样例输入 ``` 3 2 S 1 2 D 3 2 ``` ### 样例输出 ``` 10 ``` ### 评测数据规模 $2 \leq N \leq 10^5$，$1 \leq M \leq 10^5$。