shil-and-beautiful-matrix

During his interview, Shil came across a very difficult problem. The problem is as follows:  

A matrix V consisting of N rows and M columns is called beautiful if and only if it satisfies the following two conditions:  

1) Every cell of the matrix contains distinct natural number less or equal to N*M. 
2) For any two cells of the matrix, (i1,j1) and (i2,j2),   if (i1^j1) > (i2^j2) then v[i1][j1] > v[i2][j2] . 

^ denotes Bitwise XOR operation.

Note that 1 ≤ i1,i2 ≤ N and 1 ≤ j1,j2 ≤ M.

Given N and M , you have to calculatethe total number of beautiful matrices of size N x M. Since, problem is being very difficult for Shil to solve, he asks for your help.

Input format:
The Input consists of two integers N and M representing the number of rows and columns respectively.

Output format:
Output the total number of Beautiful Matrices of size N x M. Since, this answer can be large, output it modulo 10^9+7

Constraints:
1 ≤ N,M ≤ 1000

SAMPLE INPUT
2 2

SAMPLE OUTPUT
4

Explanation

The four possible matrices are:
[1 3]   |  [2 3]  | [1 4]  | [2 4]
[4 2]   |  [4 1]  | [3 2]  | [3 1]

Source: hackerearth | Difficulty: EASY
Tags: Combinatorics

Mathematics

Ad-hoc


Solutions: