Một mùa hạn hán kéo dài đã để lại cho nông dân John ~N~ cánh đồng trọc. Tuy nhiên mùa mưa cũng vừa tới, thiên nhiên đang dần phục hồi. Ở căn lều của mình, nông dân John có hai cái xô chứa hai loại hạt giống cỏ khác nhau. John muốn trồng cỏ trên ~N~ cánh đồng của mình, mỗi nơi một loại cỏ.

Là một nông dân chăn nuôi bò sữa, John muốn đảm bảo rằng anh ta đáp ứng được nhu cầu ăn khá kén chọn của ~M~ con bò. Mỗi con bò của anh ta có đúng ~2~ đồng cỏ yêu thích. Một số con bò chỉ có thể ăn đúng ~1~ loại cỏ nên ~2~ cánh đồng yêu thích của chúng phải được trồng cùng ~1~ loại cỏ. Những con bò khác cần ăn uống đa dạng nên ~2~ cánh đồng yêu thích của chúng phải được trồng ~2~ loại cỏ khác nhau.

Hãy giúp nông dân John tìm số cách trồng cỏ thoả mãn nhu cầu các con bò của mình.

Input

• Dòng đầu gồm hai số nguyên dương ~N, M~ ~(2 \le N \le 10^5, 1 \le M \le 10^5)~ là số đồng cỏ và số con bò của nông dân John.

• ~M~ dòng tiếp theo, dòng thứ ~i~ gồm kí tự ~t~ là 'S' hoặc 'D' và hai số nguyên ~a, b~ ~(1 \le a, b \le N)~, thể hiện ~2~ cánh đồng yêu thích của con bò thứ ~i~. Nếu ~t~ là 'S' thì con bò này chỉ ăn ~1~ loại cỏ, ngược lại nếu ~t~ là 'D' thì con bò này cần ăn ~2~ loại cỏ.

Output

• In ra theo hệ nhị phân số cách trồng cỏ thoả mãn nhu cầu các con bò của nông dân John.

Sample Input

3 2
S 1 2
D 3 2

Sample Output

10

Giải thích

• Có ~2~ cách trồng cỏ.