물벼룩의 생존 확률

시간 제한5초메모리 제한512 MB

요약

수직선 위 k에서 출발해 n초 동안 0에 한 번도 닿지 않고 살아남는 경로의 수 S를 구한다.

난이도: 보통10점 중 6점
유형: 조합론, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

수면에서 $k$ 센티미터 아래에 있는 물벼룩은 1초마다 각각 $1/2$ 의 확률로 위나 아래로 1센티미터 이동한다. 물벼룩은 수면에 닿는 즉시 기다리던 물매암이에게 먹혀 사라진다. $k = 0$ 이면 물벼룩은 처음부터 수면에 있으므로 곧바로 먹힌다.

예를 들어 수면 아래 2센티미터에 있던 물벼룩은 3초 동안 "위위위, 위위아래, 위아래위, ..., 아래아래아래"의 8가지 방법으로 움직일 수 있고, 각 방법의 확률은 모두 $1/8$ 로 같다. 이 가운데 "위위위"와 "위위아래"는 2초 만에 수면에 닿아 먹힌다. 나머지 6가지 경우에는 물벼룩이 수면 아래에서 살아 있으므로 3초 후 생존 확률은 $6/8$ 이다.

수면 아래 $k$ 센티미터에 있는 물벼룩이 $n$ 초 후에 살아 있을 확률이 $S/2^n$ 일 때 $S$ 를 구하시오.

입력

첫째 줄에 $k$ 와 $n$ 이 주어진다. ( $0 \le k \le n \le 63$ )

출력

첫째 줄에 $S$ 를 출력한다.

예제2

예제 1
입력
```
2 3
```
예상 출력
```
6
```
예제 2
입력
```
3 10
```
예상 출력
```
672
```