Lớp ITK19 có \(n\) học sinh nam, mỗi học sinh nam này đều crush đúng một trong ba bạn nữ: Oanh Trúc, Hương An và Tuyết Ny. Hoàng Hải từng khai thác hết thông tin crush-ship của từng bạn nam trong \(n\) bạn này và ghi chép hết chúng vào một cuốn sổ tay. Thật không may, Hải vừa đánh mất cuốn sổ của mình và rất tiếc nuối các thông tin quý giá mà mình đã dày công sưu tầm. Anh ấy chỉ còn nhớ đúng \(m\) thông tin: mỗi thông tin có dạng S u v hoặc D u v, trong đó, S u v đồng nghĩa với việc học sinh \(u\) và học sinh \(v\) cùng crush chung một người, còn D u v thể hiện rằng \(u\) và \(v\) crush hai người khác nhau.

Hải cho bạn biết \(m\) thông tin đó và nhờ bạn lập trình tính toán giúp có bao nhiêu trạng thái crush-ship thỏa mãn các ràng buộc mà anh đã nêu ra. Hãy giúp Hải nhé!

Input

• Dòng đầu chứa hai số nguyên dương \(n\) và \(m\) (\(n\leq 15\), \(m\leq 50\)).
• Mỗi dòng trong \(m\) dòng tiếp theo có dạng S u v hoặc D u v thể hiện một ràng buộc tương ứng.

Output

• Một số nguyên duy nhất là số trạng thái crush-ship thỏa mãn.

Example

4 2
S 1 2
D 1 3

18