난해한 프로그래밍 언어 BrainF**k은 +-][><,.의 여덟 가지 문자로만 작성되는 프로그래밍 언어이다.
> : 포인터를 증가시킨다.< : 포인터를 감소시킨다.+ : 포인터가 가리키는 값의 값을 증가시킨다.- : 포인터가 가리키는 값의 값을 감소시킨다.. : 포인터가 가리키는 값을 아스키 코드 문자로 출력한다., : 하나의 문자를 입력받아, 포인터가 가리키는 값을 문자의 아스키 코드 값으로 덮어쓴다.[ : 포인터가 가리키는 바이트의 값이 이라면 괄호 짝에 알맞은 ]로 이동한다.] : 포인터가 가리키는 바이트의 값이 이 아니면 괄호 짝에 알맞은 [로 이동한다.[와 ]는 반복문의 시작과 끝을 나타내며, 이 둘이 올바르게 짝지어지지 않을 때만 컴파일에 실패한다.
고양이가 키보드 위를 걷는다. 고양이가 한 걸음을 내디딜 때마다 +-][><,. 중 무작위 한 글자를 화면에 입력하게 된다.
정수 이 주어질 때, 고양이가 정확히 걸음을 걸어 만든 길이 의 문자열이 BrainF**k 코드로 컴파일될 확률을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 한 줄에 답을 출력한다.
해당 테스트 케이스의 확률을 기약분수 로 나타내자. 는 의 배수가 아니다. 을 법 에서의 의 곱셈 역원이라 할 때,
첫 번째 테스트 케이스에서는 대괄호가 아닌 여섯 문자를 입력한 경우에만 컴파일된다. 확률은 이고, 이를 법 에서 나타내면 이다.
각 케이스는 다음과 같은 형식으로 주어진다.
을 이상 미만의 정수로 출력한다.