时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H 有 \(N\) 只猴子，这 \(N\) 只猴子分别属于三个种类：A，B，C。但是不幸的是，小H 忘记了每只猴子分别属于哪个种类了。他仅仅只记得的 \(K\) 个猴子之间的关系。例如，他记得猴子 1 和猴子 2 是同一种类，或者猴子 1 和猴子 5 是不同种类的。
　　给定这 \(K\) 个关系，请帮助小H 计算这 \(N\) 只猴子可能的种类分布情况共有多少种。（当 \(K\) 个关系本身就是矛盾的时候，答案是 0 ）。

【输入格式】

　　第一行是两个正整数 \(N\) 和 \(K\)，表示猴子的数量和关系的数量。
　　接下来 \(K\) 行，每行是一个猴子种类的关系，“S x y”表示猴子x和猴子y是相同种类的，“D x y”表示猴子x和猴子y是不同种类的。

【输出格式】

　　输出满足关系条件的猴子种类分布情况共有多少种。

【输入输出样例1】

　Input

4 2 
S 1 2
D 1 3

　Output

18

【输入输出样例解释】

　　样例中，对于猴子1、猴子2、猴子3共有6种情况分别是：AAB，AAC，BBA，BBC，CCA，CCB。猴子4有3种可能，所以最终总的可能性是18种。

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤15\)，\(1≤K≤50\)。

【来源】

　　Mr.he