Indian National Olympiad in Informatics

Related:

Online Programming Contest, 4-5 June 2005

IARCS home > OLYMPIAD

Basic Division

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

and

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

and

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 N-1 and N.

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