Joshua Needs Help

View as PDF

Submit solution

Points: 10
Time limit: 0.3s
Memory limit: 64M

Author:
Problem type

Joshua is planning something and needs your help. Joshua needs your help to determine how many binary matrices of size R \times C have an even number of 1's in each row and column, modulo 10^9+7.

Input Specification

The first and only line will contain R and C (1 \le R, C \le 10^9), the number of rows and columns in the binary matrix, respectively.

Output Specification

Output the answer, modulo 10^9+7.

Sample Input 1

2 2

Sample Output 1

2

Explanation

The two matrices are:

00  11
00  11

Sample Input 2

1000000000 1000000000

Sample Output 2

949480669
Hint

If you're stuck on this problem, try finding the number of matrices for all R and C (1 \le R, C \le 5), and you might notice a pattern.


Comments