Description
Farmer John有N(2≤N≤15)头奶牛，一共有三种不同的品种，分别是:Holsteins、Jerseys和Guernseys。
FJ不能准确的记住每头奶牛的品种，但是他记得K(1≤K≤50)条一对奶牛品种之间的关系，例如，他记得奶牛1和奶牛2的品种相同，奶牛1和奶牛5的品种不同。
给出FJ的K条一对奶牛之间的关系列表，请帮助他计算出他的N头奶牛可能有多少种品种分配方案。(如果给出的关系列表中存在相互矛盾的关系，那么输出0)
Input
第一行，两个整数N和K
接下来K行，每行描述一对奶牛x和y之间的关系。格式如"S x y"表示奶牛x和y的品种相同，或者格式为"D x y"表示奶牛x和y的品种不同。(1≤x,y≤N，x!=y)
Output
一行，一个整数，可能的品种分配方案数。
HINT
【样例说明】：
一共有4头奶牛，其中奶牛1和奶牛2的品种相同，奶牛1和奶牛3的品种不同。用H、J、G分别代表Holsteins、Jerseys和Guernseys。
那么前三头奶牛的品种分别方案可以是:HHG,HHJ, GGH, GGJ, JJH, JJG,对于上述的6种方案，每种方案中，奶牛4都有三种可能的品种方案。所以4头奶牛一共有18种品种分配方案。