Một đợt hạn hán kéo dài đã khiến \(N\) đồng cỏ của Farmer John không còn chút cỏ nào. Tuy nhiên, mùa mưa sắp đến và đã tới lúc "phủ xanh trở lại". Trong nhà kho, Farmer John có hai thùng, mỗi thùng chứa một loại hạt giống cỏ khác nhau. Ông muốn trồng cỏ trên từng đồng cỏ trong số \(N\) đồng cỏ, và chọn đúng một loại cỏ để trồng trên mỗi đồng.

Là một người chăn bò sữa, Farmer John muốn bảo đảm đáp ứng những nhu cầu ăn uống có phần đặc biệt của \(M\) con bò. Mỗi con trong số \(M\) con bò có hai đồng cỏ yêu thích. Một số con có chế độ ăn yêu cầu chúng chỉ ăn nhất quán một loại cỏ — vì vậy Farmer John muốn bảo đảm hai đồng cỏ yêu thích của bất kỳ con bò nào như vậy được trồng cùng một loại cỏ. Những con bò khác có một chế độ ăn rất khác, đòi hỏi chúng phải ăn các loại cỏ khác nhau. Đối với những con bò ấy, hiển nhiên Farmer John muốn bảo đảm hai đồng cỏ yêu thích của chúng chứa hai loại cỏ khác nhau.

Hãy giúp Farmer John xác định số cách khác nhau để trồng cỏ trên \(N\) đồng cỏ.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(2 \leq N \leq 10^5\)) và \(M\) (\(1 \leq M \leq 10^5\)). Mỗi dòng trong \(M\) dòng tiếp theo chứa một ký tự là S hoặc D, theo sau là hai số nguyên trong phạm vi \(1 \ldots N\), mô tả cặp đồng cỏ yêu thích của một con bò của Farmer John. Nếu ký tự là S, dòng này biểu thị một con bò cần cùng một loại cỏ trên hai đồng cỏ yêu thích. Nếu ký tự là D, dòng này biểu thị một con bò cần hai loại cỏ khác nhau.

Dữ liệu ra

In ra số cách Farmer John có thể trồng cỏ trên \(N\) đồng cỏ. Hãy viết đáp án ở dạng nhị phân.

Ví dụ

3 2
S 1 2
D 3 2

10

Nguồn

USACO 2019 February Contest, Silver — The Great Revegetation

Tác giả: Dhruv Rohatgi và Brian Dean.