913A

 

Problem:

A. Modular Exponentiation
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

The following problem is well-known: given integers n and m, calculate

,where 2n = 2·2·…·2 (n factors), and  denotes the remainder of division of x by y.

You are asked to solve the “reverse” problem. Given integers n and m, calculate

.

Input

The first line contains a single integer n (1 ≤ n ≤ 108).

The second line contains a single integer m (1 ≤ m ≤ 108).

Output

Output a single integer — the value of .

Examples
input
4
42
output
10
input
1
58
output
0
input
98765432
23456789
output
23456789
Note

In the first example, the remainder of division of 42 by 24 = 16 is equal to 10.

In the second example, 58 is divisible by 21 = 2 without remainder, and the answer is 0.

Solution:

 

Notes:

Since 10^8 is about 24 bits, if n is larger than that, the mod operation should simply return m.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s