31780번 - 불사조

불사조는 영생을 사는 것으로 유명한 환상의 동물이다. 포닉스 역시 불사조인 만큼 영원히 살 수 있지만, 포닉스가 영생을 누리는 방법은 조금 특이하다.

포닉스는 마법을 사용해 새로운 포닉스를 만든다. 마법을 사용하는 포닉스의 마력을 $x$라고 하자. 포닉스가 마법을 사용하면 항상 $2$마리의 새로운 포닉스가 만들어지며, 새로 만들어진 포닉스 각각은 $\left\lfloor{x\over 2}\right\rfloor$와 $\left\lceil{x\over 2}\right\rceil$만큼의 마력을 가지게 된다. 한 번 마법을 사용한 포닉스는 더 이상 마법을 사용할 수 없다.

초기에는 마력이 $X$인 한 마리의 포닉스만이 존재한다. 이를 조상 포닉스라 하자. 조상 포닉스가 명령을 내리면 마법을 사용할 수 있는 모든 포닉스가 마법을 사용해 각각 $2$마리의 새로운 포닉스를 만든다. 조상 포닉스 역시 마법을 최대 한 번만 사용할 수 있기 때문에, 첫 번째 명령에서 스스로 마법을 사용한 후에는 더 이상 마법을 사용하지 않는다.

조상 포닉스의 마력 $X$와 명령을 내린 횟수 $M$이 주어질 때, 조상 포닉스를 포함한 존재하는 모든 포닉스의 마력의 합을 구하여라.

첫 번째 줄에 조상 포닉스의 마력을 나타내는 정수 $X$와 조상 포닉스가 명령을 내린 횟수 $M$이 공백으로 구분되어 주어진다. $(0\le X\le 10^8; 0\le M\le 20)$

조상 포닉스가 명령을 $M$번 내렸을 때 존재하는 모든 포닉스의 마력의 합을 출력한다.

어떤 실수 $x$에 대해, $\lfloor{x}\rfloor$는 $n \le x$을 만족하는 가장 큰 정수 $n$의 값으로 정의된다. 마찬가지로, $\lceil{x}\rceil$은 $n \ge x$을 만족하는 가장 작은 정수 $n$의 값으로 정의된다.