Из-за продолжительной засухи пастбища фермера Джона остались без травы. Однако с приближением сезона дождей пришло время "возделывать растительность". В сарае фермера Джона имеется два ведра, в каждом из которых находятся семена разной травы. Он хочет посадить траву на каждом из своих $n$ пастбищ. Каждое пастбище должно быть засеяно ровно одним видом травы. Фермер Джон, занимающийся молочным животноводством, хочет быть уверенным в том, что он удовлетворит особые диетические потребности своих $m$ коров. У каждой из его $m$ коров имеются два любимых пастбища. У некоторых коров имеется диетическое ограничение: они должны постоянно есть только один вид травы --- поэтому фермер Джон хочет, чтобы на двух любимых полях любой такой коровы был посажен один и тот же тип травы. У других коров совсем другие диетические ограничения, требующие от них есть разные виды травы. Что касается этих коров, фермер Джон, конечно же, хочет, чтобы на двух их любимых полях были разные типы травы. Помогите фермеру Джону определить количество различных способов посадки травы на его $n$ пастбищах. \InputFile Первая строка содержит числа $n~(2 \le n \le 10^5)$ и $m~(1 \le m \le 10^5)$. Каждая из следующих $m$ строк содержит символ \textbf{'S'} или \textbf{'D'}, за которым следуют два целых числа в диапазоне $1 ... n$, описывающий пару пастбищ, являющиеся любимыми для одной из коров фермера Джона. Символ \textbf{'S'} означает, что корове на ее двух любимых пастбищах нужна трава одного типа. Символ \textbf{'D'} означает, что корове на пастбищах нужны разные типы трав. \OutputFile Выведите количество способов, которыми фермер Джон может посадить траву на $n$ пастбищах. Запишите ответ в двоичном формате.