409581: GYM103637 I Items in boxes

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Items in boxestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have $$$2^n$$$ different boxes, each of them containing $$$a$$$ different items. Find the number of ways to take exactly one item from each box modulo $$$2^{n+2}$$$.

In other words, if the required number of ways is $$$x$$$, print the remainder of dividing $$$x$$$ by $$$2^{n+2}$$$.

Input

The only line of the input data contains two integers separated by a space $$$n$$$ and $$$a$$$.

$$$$$$1 \le a, n \le 10^9$$$$$$

Output

Print a single number — the remainder of dividing the number of ways to choose one item from each box by $$$2^{n+2}$$$.

ExamplesInput
5 10
Output
0
Input
10 5
Output
1
Input
1 2
Output
4
Note

In the third example, $$$2^n=2$$$ boxes, each with $$$a=2$$$ items. It turns out that there are two ways to take an item from the first and two ways to take an item from the second, total $$$2 \cdot 2=4$$$ of the method. The remainder of the division by $$$2^{n+2}=2^{3}=8$$$ is $$$4$$$.

加入题单

上一题 下一题 算法标签: