Given the first positive integers, there are
non-empty subsets. Bob wants to choose
distinct subsets from them so that each integer in the union of the
subsets occurred an even number of times. For example, if
and
, there are
non-empty subsets. Bob can choose the subsets
,
, and
, where every integer has an even number of occurences. Can you help Bob to find the number of different ways to choose the
subsets? Since the answer is huge, ouptut the answer modulo
.
Input Specification
The first line of input contains two integers and
(
).
Output Specification
Output one integer, the number of ways to choose subsets.
Constraints
Subtask | Points | Additional constraints |
---|---|---|
No additional constraints. |
Sample Input 1
3 3
Sample Output 1
7
Explanation
There are ways to choose
subsets, listed as following:
,
,
,
,
,
,
,
,
,
,
,
,
,
,
Sample Input 2
5 3
Sample Output 2
155
Comments