题目描述

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

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

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

输入格式

输入的第一行包含两个整数 $N$（$2\le N\le10^5$）和 $m$（$1\le m\le10^5$）。

之后 $m$ 行，每行描述了一头奶牛。首先是一个字符 S 或 D，表示这头奶牛需要相同（S）还是不同（D）的草类型，然后是两个 $1\sim N$ 的整数，表示这头奶牛喜欢的两块牧场。

输出格式

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

3 2
S 1 2
D 3 2

10

提示

USACO 2019 二月月赛银牌组第三题