Тренер Ильнур перед летом решил натренировать своих хомяков

Тренер Ильнур перед летом решил натренировать своих хомяков. Ильнур подготовил два типа тренажеров. Тренер хочет подготовить N
спортзалов для тренировок. Для каждого спортзала надо выбрать только один тип тренажеров.
У тренера M
хомяков. Каждый хомяк любит только две тренажерки.
Некоторые из хомяков физически слабые и могут заниматься только на одном типе тренажеров. Поэтому Ильнур должен обеспечить один и тот же тип тренажеров в обоих любимых спортзалах каждого хомяка.
Физически готовые хомяки должны тренироваться на разных типах тренажеров. Для этих хомяков Ильнур должен обеспечить, чтобы оба их любимых спортзала содержали разные типы тренажеров.
Определите количество различных способов, которыми Ильнур может подготовить N
спортзалов, по модулю 1000000007
.
Входные данные
Первая строка содержит два натуральных числа N
(2?N?105
) и M
(1?M?105
).
Каждая следующая из M
строк содержит символ 'S' или 'D' и два натуральных числа ai
и bi
(1?ai,bi?N
). Пара чисел описывает любимые спортзалы i
-го хомяка, а символ 'S' означает, что хомяк должен тренироваться на одном типе тренажеров в обоих своих спортзалах, символ 'D' означает, что хомяк должен тренироваться на разных типах тренажеров в обоих своих спортзалах.
Выходные данные
Выведите количество различных способов, которыми Ильнур может подготовить N
спортзалов, по модулю 1000000007
.
Пример
входные данные
3 2
S 1 2
D 3 2
выходные данные
2
C++