문제

메모리 제한에 주의해주세요.

한양대학교 컴퓨터소프트웨어학부의 과탑인 임세훈는 인기 유튜브 채널 B-Stream에 출연하게 되었다.

세훈이가 참여하는 코너는 LCG Madness!로, 아래와 같은 규칙을 따른다.

• 시작하기 전, 개의 LCG와 개의 동전을 준비한다.
• 모든 LCG를 초기화한다. 정확히는, 모든 에 대해 의 값을 로 설정한다.
• 모든 동전을 진행자 마음대로 놓는다.
• 번의 라운드동안 아래 과정을 반복한다.
  1. 모든 LCG를 실행한다. 정확히는, 모든 에 대해 의 값이 로 변경된다.
  2. 참가자가 개의 LCG 중 하나를 선택한다. 설명을 위해, 번째 LCG를 선택했다고 하자.
  3. 번째 동전을 뒤집는다. 만약 앞면이었다면 뒷면으로, 뒷면이었다면 앞면이 된다.
  4. 번째 동전과 같은 면을 보이고 있는 동전들의 위치를 각각 라고 할 때, 참가자가 받는 돈에 달러가 추가된다.

세훈이는 여기서 최대한 많은 돈을 받아가려고 한다. 세훈이를 도와 최대 얼마까지 받아갈 수 있는지 찾아보자!

입력

첫째 줄에는 과 이 주어진다.
둘째 줄에는 개의 동전이 놓인 면을 의미하는 이 공백 없이 주어진다. 는 H 또는 T
이어 둘째 줄부터 개의 줄에 걸쳐서 LCG의 정보 가 공백을 사이에 두고 주어진다.

출력

세훈이가 최대 얼마를 받을 수 있는지 달러 단위로 출력한다.