Survival Probability of a Water Flea

Time limit5sMemory limit512 MB

Summary

Count the paths of length n on a line starting at k that never return to 0, so the survivor count is S in S/2^n.

Level: Medium6 of 10
Topics: Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

A water flea is $k$ centimeters below the water surface. Every second it moves 1 centimeter up or 1 centimeter down, each with probability $1/2$ . The moment the water flea touches the surface, the whirligig beetles waiting there eat it. If $k = 0$ , the water flea starts on the surface and is eaten immediately.

For example, a water flea 2 centimeters below the surface can move in 8 ways over 3 seconds: "up up up, up up down, up down up, ..., down down down". Each of these ways has the same probability $1/8$ . In the ways "up up up" and "up up down", the water flea reaches the surface after 2 seconds and is eaten. In the other 6 ways it stays alive below the surface, so its survival probability after 3 seconds is $6/8$ .

The probability that a water flea $k$ centimeters below the surface is still alive after $n$ seconds is $S/2^n$ . Compute $S$ .

Input

The first line contains $k$ and $n$ . ( $0 \le k \le n \le 63$ )

Output

Print $S$ on the first line.

Examples2

Example 1
Input
```
2 3
```
Expected output
```
6
```
Example 2
Input
```
3 10
```
Expected output
```
672
```