민수의 화로에는 홀수 개의 양꼬치 개가 일렬로 놓여 있다. 위에서 번째 위치의 온도는 이다. 양꼬치가 분 동안 받는 열량은 현재 위치의 온도와 같다.
민수는 모든 양꼬치를 분 동안 굽고, 서로 다른 두 양꼬치의 위치를 교환하는 작업을 원하는 만큼 수행한 뒤, 다시 모든 양꼬치를 분 동안 굽는다. 각 양꼬치의 최종 열량은 두 번의 가열에서 받은 열량의 합이다.
각 양꼬치의 손잡이는 왼쪽(L) 또는 오른쪽(R)을 향한다. 손잡이 방향이 서로 반대인 두 양꼬치만 교환할 수 있고, 한 번 교환에 참여한 양꼬치는 다시 교환할 수 없다.
다음은 , RLLRLRR일 때 위에서 본 화로와 각 양꼬치의 손잡이 방향을 나타낸 그림이다.
최종 열량의 최댓값과 최솟값의 차이를 이하로 만들면서 교환 횟수를 최소화하려 한다. 교환 순서만 다른 경우는 같은 방법으로 본다. 이때 가능한 서로 다른 교환 쌍 집합의 수를 구해 보자.
첫째 줄에 홀수 이 주어진다. ()
둘째 줄에 길이 의 문자열 가 주어진다. 는 번째 양꼬치의 손잡이 방향이며 또는 이다.
조건을 만족하면서 교환 횟수가 최소인 방법의 수를 로 나눈 나머지를 출력한다. 가능한 방법이 없다면 을 출력한다.
LR입력으로 주어지는 모든 수는 정수이다.