Problem 2: Find the
Distance, *(Tanmoy Chakraborty, Indraneel Mukherjee, CMI)*

Given two numbers written out in binary with the same number of binary
digits, the *Hamming distance* between them is the number of
positions where they differ. For example the Hamming distance between

010010

and

100010

is 2 since they differ in the leftmost two positions and nowhere else. Similarly the Hamming distance between

0111110

and

0011100

is 2.

Suppose we consider binary numbers of length *K*. Given a
number *N* with *N ≤ 2 ^{K} - 1*, we want to
find the sum of the Hamming distances between 0 and 1, 1 and 2 and so
on till

For example if *K*=3 and *N*=4 the answer is 7 since
the Hamming distance between 000 and 001 (0 and 1 written using 3
bits) is 1, the distance between 001 and 010 is 2, between 010 and 011
is 1 and between 011 and 100 is 3.

Given *K* and *N*, your task is to find the sum of
the Hamming distances between the *K*-digit binary representations of 0
and 1, 1 and 2, ..., *N-1* and *N*.

Input format

A single line with two positive integers *K* and *N*.

Output format

A single line with a single integer giving the required sum of Hamming distances.

Test data

You may assume that *K ≤ 32* and *N ≤
1000000*.

Example

We now illustrate the input and output formats using the above example.

Sample input

3 4

Sample output

7

Copyright (c) IARCS 2003-2020; Last Updated: 05 Jul 2005