题目描述

长时间的干旱使得农夫约翰的 $N$块草地上牧草匮乏。

随着雨季即将到来，现在应当是重新种植的时候了。

在约翰的储物棚里有两个桶，每个桶里装着一种不同的草种。

他想在自己的 $N$ 个牧场中都种上草，并且每种牧场中只选择一种草来种植。

作为一个奶农，他希望确保自己能够满足自己的 $M$ 头奶牛的某些特殊饮食需求。

这 M头奶牛中的每头牛都有自己最喜欢的两个牧场。

其中一些奶牛有一个饮食限制，就是它们只能吃一种类型的草。

对于这些奶牛，约翰希望确保它们中的任意一头奶牛最喜欢的两个牧场里都种着同一类型的草。

其他奶牛的饮食限制跟上述奶牛又有所不同，这些奶牛喜欢吃不同类型的草。

对于这些奶牛，约翰希望确保它们中的任意一头奶牛最喜欢的两个牧场里都种着不同类型的草。

请帮助约翰确定他在这 $N$ 个牧场上种草的不同方法的数量。

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行都包含一个字符 $S$ 或 $D$，后跟两个整数，范围在 $1…N$，用来描述一头牛的类型以及它最喜欢的两个牧场的编号。如果字符为 $S$，则表示这是喜欢吃同一类型的草的牛，如果字符为 $D$，则表示这是喜欢吃不同类型的草的牛。

输出格式

输出农民约翰在他的 $N$ 个牧场上种草的不同方法的数量。

请用二进制形式输出你的答案。

样例

3 2
S 1 2
D 3 2​

10​

提示

$2≤N≤10^5$,

$1≤M≤10^5$