Joshua Needs Help

View as PDF

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 have an even number of 's in each row and column, modulo .

Input Specification

The first and only line will contain and , the number of rows and columns in the binary matrix, respectively.

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 and , and you might notice a pattern.