지하철 통과 운행표

문제

지하철 운영팀은 시험 열차 한 편의 통과 운행표를 작성한다. 열차는 출발역을 떠난 뒤 중간역 N개를 순서대로 지나 종착역에 도착한다. 출발역과 종착역에서는 반드시 정차하며, 이 두 역은 입력과 운행표에 포함하지 않는다. 운영팀이 결정할 것은 각 중간역에서 정차할지 통과할지뿐이다. 역을 방문하는 순서와 선로는 고정되어 있다. 운행표는 길이가 N인 이진 문자열로 나타낸다. 왼쪽부터 i번째 문자가 0이면 i번째 중간역에 정차하고, 1이면 그 역을 정차하지 않고 통과한다. 시험 조건을 맞추기 위해 정확히 K개의 중간역을 통과해야 한다. 또한 승객 안내 장치가 연속 통과를 지원하지 않으므로 서로 이웃한 두 중간역을 모두 통과할 수 없다. 따라서 운행표에는 부분 문자열 `11`이 나타나면 안 된다. 첫 번째 중간역과 마지막 중간역은 서로 이웃한 것으로 취급하지 않는다. 각 중간역에는 별도의 정차 제한이 주어진다. 제한 문자열의 i번째 문자가 S이면 해당 역에는 반드시 정차해야 하므로 운행표의 i번째 문자는 0이어야 한다. 제한 문자가 F이면 정차와 통과 중 어느 쪽이든 선택할 수 있다. F인 역에서도 정확한 통과 횟수와 연속 통과 금지 규칙은 지켜야 한다. 제한 문자열은 역의 상태를 알려 줄 뿐이며, F인 역을 반드시 통과하라는 뜻은 아니다. 운영팀은 조건에 맞는 모든 운행표의 수를 확인한 뒤 가장 앞선 운행표 하나를 검토하려 한다. 운행표 두 개는 어느 한 위치의 문자가 다르면 서로 다른 것으로 센다. 사전순에서는 문자 0이 문자 1보다 앞선다. 따라서 두 운행표를 왼쪽부터 비교했을 때 처음 다른 위치에서 0을 가진 운행표가 앞선다. 조건을 만족하는 운행표의 수와 사전순으로 가장 앞선 운행표를 구해야 한다. 가능한 운행표가 없다면 개수 0과 함께 지정된 문자열을 출력한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1≤N≤20이고 0≤K≤N이다. 둘째 줄에 길이가 N인 제한 문자열이 주어진다. 문자열의 각 문자는 S 또는 F다.

출력

첫째 줄에 조건을 만족하는 운행표의 수를 출력한다. 둘째 줄에 사전순으로 가장 앞선 운행표를 출력한다. 가능한 운행표가 없다면 둘째 줄에 `NONE`을 출력한다. 운행표의 앞쪽에 있는 0도 모두 출력해야 한다.

4 2
FFFF

3
0101

3 2
FSF

1
101

3 1
SSS

0
NONE

출처: Devin.KR 자체 제작