품종 배정

농부 John에게는 소 $N$마리($2 \le N \le 15$)가 있으며, 각 소는 홀스타인(Holstein), 저지(Jersey), 건지(Guernsey) 세 품종 중 하나입니다.

안타깝게도 John은 각 소의 정확한 품종을 기억하지 못합니다. 다만 소 쌍 사이의 관계 $K$개($1 \le K \le 50$)는 기억하고 있습니다. 예를 들어 1번 소와 2번 소가 같은 품종이라거나, 1번 소와 5번 소가 서로 다른 품종이라는 식입니다.

John이 기억하는 소 쌍 사이의 관계 목록이 주어질 때, 소들에게 품종을 배정하는 서로 다른 방법의 수를 구하세요. (관계 목록이 서로 모순된다면 이 값은 $0$이 될 수 있습니다.)

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $K$.
• 둘째 줄부터 $K$개의 줄: 각 줄은 두 소 $x$와 $y$($1 \le x, y \le N$, $x \ne y$)의 관계를 나타냅니다. S x y 형식은 $x$와 $y$가 같은 품종임을, D x y 형식은 $x$와 $y$가 서로 다른 품종임을 뜻합니다.

• 첫째 줄: 가능한 품종 배정의 수.

예를 들어 소가 $4$마리이고, 1번과 2번 소가 같은 품종이며 1번과 3번 소가 서로 다른 품종이라고 합시다. 앞의 세 소에 대해 가능한 품종 배정은 HHG, HHJ, GGH, GGJ, JJH, JJG의 여섯 가지입니다. 각 경우에 대해 4번 소는 아무 제약이 없어 세 품종 중 무엇이든 될 수 있으므로, John의 목록과 일치하는 배정은 총 $6 \times 3 = 18$가지입니다.