E. Ratman's Puzzle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ratman is attempting to save the city from one of his most dangerous nemeses, the Puzzler! Unfortunately, the Puzzler has distributed various bombs around Ratman's hometown, Gothem city, and Ratman must solve a series of math puzzles to defuse each bomb.

Specifically, each bomb is labelled with two numbers $$$n$$$ and $$$k$$$. For each bomb, Ratman must calculate the number of pairs of integers $$$a, b$$$ with $$$0 \leq a < b < 2^k$$$ such that $$$a \oplus b = n$$$, where $$$\oplus$$$ denotes the XOR operator. After doing so, he can plug the result into his bomb-defusing machine, which will neutralize the threat if the number is calculated correctly.

Write a program to help Ratman solve the Puzzler's riddles and defuse the bombs throughout Gothem city!

Input

The input will consist of two numbers $$$n$$$ $$$(1 \leq n \leq 10^{18})$$$ and $$$k$$$ $$$(1 \leq k \leq 60)$$$.

Output

Output the number of distinct pairs of integers $$$a, b$$$ such that $$$0 \leq a < b < 2^k$$$ and $$$a \oplus b = n$$$.

Examples
Input
7777 1
Output
0
Input
3 2
Output
2
Note

In the first sample, the only possible pair is $$$a = 0, b = 1$$$ and $$$0 \oplus 1 = 1 \neq 7777$$$.

In the second sample, there are two pairs that satisfy the above property. Specifically $$$a = 0, b = 3$$$ and $$$a = 1, b = 2$$$ both work.