Shil and Beautiful Matrix

4.1

42 votes
Combinatorics, Ad-Hoc, Easy, Mathematics, Open, Approved
Problem

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 109+7

Constraints:
1 ≤ N,M ≤ 1000

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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

Editor Image

?