题目描述

农夫约翰有N头奶牛（2 ≤ N ≤ 15），每头奶牛可能属于三个品种之一：荷斯坦牛（Holstein）、泽西牛（Jersey）或根西牛（Guernsey）。

不幸的是，约翰记不清每头奶牛的具体品种了！但他记得K对奶牛之间的品种关系：例如，他可能记得奶牛1和2是同品种的，或者奶牛1和5是不同品种的。

根据约翰记录的奶牛品种关系，请计算可能的品种分配方案总数（如果记录中存在矛盾信息，则结果为0）。

输入格式

第一行：两个空格分隔的整数N和K

接下来K行：每行描述一对奶牛的关系，格式为：

• "S x y" 表示奶牛x和y同品种
• "D x y" 表示奶牛x和y不同品种 （1 ≤ x,y ≤ N，x ≠ y）

输出格式

一个整数，表示满足条件的品种分配方案数

输入输出样例

输入 #1

4 2
S 1 2
D 1 3

输出 #1

18

样例解释

有4头奶牛，已知：

1. 奶牛1和2同品种
2. 奶牛1和3不同品种

前3头奶牛的可行分配方案有6种：

• HHG, HHJ
• GGH, GGJ
• JJH, JJG

对于每种前3头奶牛的分配方案，第4头奶牛有3种可能的品种选择（H/J/G），因此总共有6×3=18种满足条件的分配方案。