### 问题描述 农夫小齐养了 $N$ 头奶牛 $(2 \leq N \leq 15)$，它们分别属于三种不同品种：荷斯坦牛（$Holsteins$）、泽西牛（$Jerseys$）或根西牛（$Guernseys$）。 不幸的是，小齐忘记了每头奶牛的具体品种！然而，他还记得一份包含 $K$ 条 $(1 \leq K \leq 50)$ 关于奶牛品种关系的清单；例如，他可能记得奶牛 $1$ 和 $2$ 属于相同品种，或者奶牛 $1$ 和 $5$ 属于不同品种。 给定小齐关于奶牛品种关系的清单，请帮助他计算可能的不同品种分配数（如果清单中包含矛盾信息，可能的分配数为零）。 ### 输入格式 第 $1$ 行：两个由空格分隔的整数 $N$ 和 $K$。 接下来 $K$ 行：每行描述一对奶牛 $x$ 和 $y$ 的关系。关系形式为 "$S$ $x$ $y$"，表示奶牛 $x$ 和 $y$ 属于相同品种，或者 "$D$ $x$ $y$"，表示奶牛 $x$ 和 $y$ 属于不同品种。 ### 输出格式 可能的不同品种分配数。 ### 样例输入 ``` 4 2 S 1 2 D 1 3 ``` ### 样例输出 ``` 18 ``` ### 评测数据规模 $1 \leq x, y \leq N, x \neq y$，$2 \leq N \leq 15$。