Being a dairy farmer, Farmer John wants to make sure he manages the somewhat particular dietary needs of his M cows. Each of his MM cows has two favorite pastures. Some of his cows have a dietary restriction that they should only eat one type of grass consistently --- Farmer John therefore wants to make sure the same type of grass is planted in the two favorite fields of any such cow. Other cows have a very different dietary restriction, requiring them to eat different types of grass. For those cows, Farmer John of course wants to make sure their two favorite fields contain different grass types.
Please help Farmer John determine the number of different ways he can plant grass in his N pastures.
The first line of input contains N (2≤N≤10^5) and MM (1≤M≤10^5). Each of the next MM lines contains a character that is either 'S' or 'D', followed by two integers in the range 1…N, describing the pair of pastures that are the two favorites for one of Farmer John's cows. If the character is 'S', this line represents a cow that needs the same type of grass in its two favorite pastures. If the character is 'D', the line represents a cow that needs different grass types.
Output the number of ways Farmer John can plant grass in his N pastures. Please write your answer in binary.