题目描述

强哥 有 $N$ （ $2 \le N \le 15$ ）头奶牛，每头奶牛的品种是荷斯坦牛、泽西牛或者根西牛。

不幸的是， 强哥 不记得每头奶牛的具体品种了！然而，他记得 $K$ （ $1 \le K \le 50$ ）对奶牛之间的关系。例如，他可能记得奶牛 $1$ 、 $2$ 是同一品种，或者奶牛 $1$ 、 $5$ 是不同品种。

给定 强哥 已知的一些奶牛之间的关系，请帮助他求出有多少种可能的奶牛品种分配方法。当奶牛之间的关系出现矛盾时，答案为 $0$ 。

输入格式

第 $1$ 行：两个整数 $N$ 、 $K$ ，用空格分隔。

第 $2 \dots K + 1$ 行：每行描述了奶牛 $x$ 、 $y$ （ $1 \le x, y \le N, x \neq y$ ）之间的关系，数据形式要么为 S x y ，表示 $x$ 、 $y$ 是同一品种，或者为 D x y ，表示 $x$ 、 $y$ 是不同品种。

输出格式

第 $1$ 行：一个整数，表示奶牛品种分配方法种数。

4 2
S 1 2
D 1 3

18

提示

样例解释

有 $4$ 头奶牛，其中奶牛 $1$ 、 $2$ 是同一品种，奶牛 $1$ 、 $3$ 是不同品种。对于奶牛 $1$ 、 $2$ 、 $3$ ，一共有 $6$ 种可能的奶牛品种分配方法： HHG 、 HHJ 、 GGH 、 GGJ 、 JJH 、 JJG 。对于这 $6$ 种分配方法，奶牛 $4$ 可能是任意一种奶牛，因此一共有 $18$ 种可能的奶牛品种分配方法。

H 、 J 、 G 分别表示荷斯坦牛、泽西牛、根西牛。