JOIN
Get Time

   Problem Statement  

 Problem Statement for WinterAndSnowmen

Problem Statement

    

It's winter time! Time for snowmen to play some games.

Two snowmen are playing a game. In this game, the first snowman must choose a subset of the set {1, 2, ..., N}, and the second one must choose a subset of the set {1, 2, ..., M}. The following two conditions must be fulfilled:

  • The two sets have an empty intersection.
  • The XOR of all elements in the first set is less than the XOR of all elements in the second set.

You are given two ints N and M. Let X be the total number of different ways to choose the pair of sets. Return the value (X modulo 1,000,000,007).

 

Definition

    
Class:WinterAndSnowmen
Method:getNumber
Parameters:int, int
Returns:int
Method signature:int getNumber(int N, int M)
(be sure your method is public)
    
 

Notes

-XOR (exclusive or) is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers differ the result has 1 in its binary representation. It has 0 in all other positions.
-For example 42 XOR 7 is performed as follows. First, the numbers are converted to binary: 42 is 101010 and 7 is 111. Then the shorter number is prepended with leading zeros until both numbers have the same number of digits. This means 7 becomes 000111. Then 101010 XOR 000111 = 101101 (the result has ones only in the positions where the two numbers differ). Then the result can be converted back to decimal notation. In this case 101101 = 45, so 42 XOR 7 = 45.
-The XOR of an empty set is 0.
 

Constraints

-N will be between 1 and 2000, inclusive.
-M will be between 1 and 2000, inclusive.
 

Examples

0)
    
2
2
Returns: 4
The following 4 pairs of subsets are possible in this case:
  • {} and {1}
  • {} and {2}
  • {} and {1, 2}
  • {1} and {2}
1)
    
1
1
Returns: 1
The only pair possible in this case is {} and {1}.
2)
    
3
5
Returns: 74
3)
    
7
4
Returns: 216
4)
    
47
74
Returns: 962557390

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 601 Round 1 - Division I, Level Two