Joshua Needs Help

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 0.3s

Memory limit: 64M

Author:

kevinyang

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$ $R \times C$ have an even number of $1$ $1$ 's in each row and column, modulo $10^9+7$ $10^{9} + 7$ .

Input Specification

The first and only line will contain $R$ $R$ and $C$ $C$ $(1 \le R, C \le 10^9)$ $(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$ $10^{9} + 7$ .

Sample Input 1

Copy

2 2

Sample Output 1

Copy

Explanation

The two matrices are:

Copy

00  11
00  11

Sample Input 2

Copy

1000000000 1000000000

Sample Output 2

Copy

949480669

Hint

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

Comments

1

Kevy3030 commented on Oct. 3, 2020, 3:14 p.m.

JoshyBoi this u?

4

kevinyang commented on Oct. 3, 2020, 3:33 p.m.

https://dmoj.ca/problem/kevin :D