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\leq R,C\leq 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
00

11
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\leq R,C\leq 5), and you might notice a pattern.


Comments