AT_discovery_2016_final_d ディスコ社内ツアーⅡ

给定一个 $N$ 个顶点， $M$ 条边的有向图，第 $i$ 条边会被记为 `O` 或 `E`。 遍历由顶点 $s$ 开始，至 $t$ 结束。 图中的边若被记为 `O` ：则该条边可以通过奇数次； 若被记为 `E` ：则该条边可以通过偶数次（可为 $0$ 次）。 询问遍历有多少种走法。

格式如下： 第一行给出两个数 $N$，$M$ $(2 \le N \le 200，1\le M \le N(N-1))$。 接下来 $M$ 行，每行有两个数和一个字符 `O` 或 `E` ，分别表示起点 $s$ 和终点 $t$ ，和该边被标记的类型。 给出的图不含有重边和自环。

输出答案表示方案总数。 **谢谢！**

### Sample Explanation 1 \- このケースにおいては頂点 $ 1 $ から頂点 $ 2 $ に向かって移動したとき、条件を満たします。答えは $ (1,2) $ の $ 1 $ 通りであり、それ以外には存在しません。 ### Sample Explanation 2 \- このケースにおいては出発直後に条件を満たしています。答えは $ (1,1),\ (2,2) $ の $ 2 $ 通りであり、それ以外には存在しません。 - `E`のラベルがついた辺は $ 0 $ 回通ってもよいことに注意してください。 ### Sample Explanation 3 \- このケースにおいては頂点 $ 1 $ から頂点 $ 2 $ に向かって移動したとき、条件を満たします。答えは $ (1,2) $ の $ 1 $ 通りであり、それ以外には存在しません。 - `E`のラベルがついた辺は $ 0 $ 回通ってもよいことに注意してください。 ### Sample Explanation 4 \- このケースにおいては、どのように移動しても条件を満たすことはできません。 - `O`のラベルがついているような辺はそれぞれ奇数回通らなくてはならないこと、`E`のラベルがついているような辺はそれぞれ偶数回通らなくてはならないことに注意してください。