该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Farmer John 有 N 头奶牛($2 \le N \le 15$)，每头奶牛属于下面三个品种中的一个：Holsteins 荷斯坦牛, Jerseys 泽西种乳牛, Guernseys 格恩西种奶牛。不幸的是，Farmer John 记不清他的奶牛们确切的品种。但是，他记得奶牛们之间K 个关系的名单($1 \le K \le 50$)。例如，他记得，奶牛 1 和奶牛 2 有相同的品种，奶牛1 和奶牛 5 是不同的品种。

现在给 Farmer John 一个奶牛们之间 $K$ 个关系的列表，请帮助他计算不同情况下奶牛们的品种的情况个数（如果列表中包含矛盾的信息，那么这个数可能为 0）

Input Format

第 1 行：两个空格隔开的整型数：$N$ 和 $K$。

第 $2 \cdots 1+K$ 行：每行描述了奶牛 $x$ 和奶牛 $y$ 之间的关系($1 \le x,y \le N, x != y$)。

形如“S x y”表示 $x$ 和 $y$ 有着相同的品种，形如“D x y”表示 $x$ 和 $y$ 是不同的品种。

Output Format

一行，为可能的品种安排情况个数。

Sample

【样例输入】

4 2
S 1 2
D 1 3

【样例输出】

18

【样例解释】

现在有 4 头奶牛。奶牛 1 和奶牛 2 是相同的品种，奶牛 1 和奶牛 3 是不同的品种。下面六种品种安排情况是前 3 头奶牛的情况：HHG，HHJ,GGH,GGJ,JJH,JJG。在每种情况下，我们可以有 3 种品种安排给第 4 头奶牛，则根据列表总共有 18 种不同的品种安排方式。