A culture initially contains \(N\) cells. Every second, each cell divides into two cells. Determine the population after \(T\) seconds.

Input

The first line contains \(N\). The second line contains \(T\).

The input satisfies:

• \(0 \le N \le 10^20\)
• \(0 \le T \le 1000\)

Output

Print the number of cells after \(T\) seconds.

Example

Input

89065289489201785001
4

Output

1425044631827228560016