题目描述

漫长的干旱使Farmer John的N牧场没有草。然而，随着雨季即将到来，现在是“重新开始”的时候了。在Farmer John的棚子里，他有两个桶，每个桶都有不同类型的草籽。他想在他的N个牧场中种植草，每个牧场都选择一种草种。

作为一名奶农，Farmer John希望确保他能够管理他的M奶牛的某些特殊饮食需求。他的每头奶牛都有两个最喜欢的牧场。他的一些奶牛有一个饮食限制，他们应该只吃一种类型的草 - 农民约翰因此想要确保在任何这样的奶牛的两个最喜欢的领域种植相同类型的草。其他奶牛有不同的饮食限制，要求他们吃不同类型的草。对于那些奶牛，Farmer John当然希望确保他们最喜欢的两个田地包含不同的草类型。

请帮助Farmer John确定他在N牧场种草的不同方式。

输入格式

第一行输入包含N（2≤N≤100000）和M（1≤M≤100000）。接下来的M行中的每一行都包含一个“S”或“D”字符，后面跟着1 ... N范围内的两个整数，描述了一对牧场，它们是Farmer John奶牛之一的两个最爱。如果角色是'S'，则该线代表在其两个最喜欢的牧场中需要相同类型草的母牛。如果角色为'D'，则该线代表需要不同草类型的母牛。

输出格式

输出农民约翰可以在他的N牧场种植草的方式。请以二进制形式写下你的答案。

输入样例

3 2
S 1 2
D 3 2

输出样例

10