경비병 피하기

새로운 게임을 해 보자. 당신과 친구들로 이루어진 팀이 일렬로 늘어선 경비병들 사이를 차례로 지나간다. 놀이터 게임 "Rover, Red Rover."와 비슷하다. 경비병은 앞, 왼쪽, 오른쪽 중 한 방향을 보고 있다. 앞을 보는 경비병은 주변 시야가 매우 좁아서, 다가오는 사람을 너무 늦게까지 보지 못한다(눈가리개를 쓰고 있을지도 모른다). 옆을 보고 있으면서 당신이 지나갈 때 등을 돌리고 있는 경비병도 마찬가지로 보지 못한다. 하지만 한 쌍의 경비병 사이를 지나는 순간, 그들은 소리를 듣고 당신이 지나간 틈을 향해 돌아선다. 그래서 같은 쌍 사이를 다시 지나가려 하면 막을 수 있는 위치에 서 있게 된다. 플레이어가 통과하려는 틈을 두 경비병 중 한 명이라도 향하고 있으면, 그 플레이어는 막힌다.

형식적으로 정리하면 다음과 같다. 경비병은 왼쪽에서 오른쪽으로 $1$번부터 $g$번까지 번호가 붙는다. 각 플레이어는 경비병 $i$와 $i+1$ 사이의 틈을 지나기로 선택한다($1 \leq i \leq g-1$). 플레이어는 첫 번째 경비병의 왼쪽이나 마지막 경비병의 오른쪽으로 갈 수 없다. 경비병 $i$가 오른쪽을 보고 있거나 경비병 $i+1$이 왼쪽을 보고 있으면(둘 다일 수도 있다) 플레이어는 잡힌다. 그렇지 않으면 경비병 $i$는 오른쪽을, 경비병 $i+1$은 왼쪽을 향하도록 돌아선다. 다른 경비병의 방향은 바뀌지 않는다.

경비병들의 처음 방향과 팀의 플레이어 수 $p$가 주어질 때, 모든 플레이어가 잡히지 않고 경비병들을 지나갈 수 있는가?

첫 줄에 양의 정수 두 개가 주어진다. 경비병의 수 $g$ ($2 \leq g \leq 10$)와 플레이어의 수 $p$ ($1 \leq p \leq 50$)이다. 둘째 줄에는 각 경비병이 처음 보고 있는 방향을 나타내는 대문자 문자열이 주어진다. 각 문자는 L(왼쪽), F(앞), R(오른쪽) 중 하나이다.

최적으로 행동했을 때 모든 플레이어 $p$명이 잡히지 않고 지나갈 수 있으면 1을, 그렇지 않으면 0을 출력한다.