一场漫长的干旱使农场主约翰的N牧场没有草。然而，随着雨季的到来，是时候“重新种植”了。在农夫约翰的小屋里，他有两个桶，每个桶都有不同类型的草籽。他想在他的每一个N牧场种草，在每一个牧场中选择一种类型的草。

作为一名奶农，农场主约翰想确保他能满足他那几头奶牛的特殊饮食需求。他的每m头奶牛都有两个最喜欢的牧场。他的一些奶牛有一个饮食限制，那就是他们应该只吃一种类型的草，因此农场主约翰希望确保在这类奶牛最喜欢的两个田里种植同一种类型的草。其他的奶牛有一个非常不同的饮食限制，要求他们吃不同类型的草。对于那些奶牛，农场主约翰当然想确保他们最喜欢的两块田地里有不同的草。

请帮助农场主约翰确定他在他的N牧场上种植草的不同方式的数量。

输入格式（文件 revegetate.in）：

输入的第一行包含$N (2≤N≤10^5)$和$M (1≤M≤10^5）$。下一行m中的每一行都包含一个“s”或“d”字符，后跟两个1…n范围内的整数，描述农场主约翰的一头牛最喜欢的两个牧场。如果字符是“S”，则这一行表示一头母牛在其两个最喜爱的牧场中需要相同类型的草。如果字符为“D”，则该行表示需要不同草类型的奶牛。

输出格式（文件 revegetate.out）：

输出农场主约翰在他的N牧场上植草的方式。请用二进制写你的答案。

SAMPLE INPUT:

3 2
S 1 2
D 3 2

SAMPLE OUTPUT:

10