Too Simple

4.6

18 votes
Hard
Problem

Vaibhav likes to play with sequences and do bitwise operations on it. He is interested in two types of sequences A and B. Sequence A consists of distinct integers lying between 1 and n (both inclusive) and sequence B consists of distinct integers lying between 1 and m (both inclusive). Formally, A is a subset of {1, 2, ...,n} and B is a subset of {1, 2, ...., m}. Size of sequences can be zero. He wants to find total number of different pairs of sequences A and B such that their intersection is an empty set and bitwise-XOR of all elements of A is strictly less than bitwise-XOR of all elements of B. Help him find the answer! As the answer can be very large, print answer modulo 1000000007.

Input Format

Input contains only two integers n and m as mentioned in problem.

Output Format

Output should contain the total number of possible pairs of A and B as per mentioned conditions modulo 1000000007.

Constraints

  • 1 <= n <= 2000
  • 1 <= m <= 2000

Author : Tanmay Patel

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Following are 4 possible pairs of A and B:

A = { } , B = {1} : XOR of A = 0, XOR of B = 1

A = { } , B = {2} : XOR of A = 0, XOR of B = 2

A = { } , B = {1, 2} : XOR of A = 0, XOR of B = 3

A = {1} , B = {2} : XOR of A = 1, XOR of B = 2

Editor Image

?