DMOPC '14 Exam Time P6 - Math Homework

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

One morning, you realize that binary matrices are irresistible. You just can't stop thinking about them. You realize that you had inherited your love of binary matrices from your math teacher, Mr. Sidhu!

Thinking back a little, this is because Mr. Sidhu had left you a homework problem to be completed by last period today. And you didn't even start on it! Luckily, you have a few minutes before class starts. You take a look at the problem again:

Determine the number of binary matrices of size R \times C that have at least one 1 entry in each row and column, modulo 10^9+7.

Since there are a lot of problems of this form, specifically T of these problems, you would like to write a program that solves these quickly, or risk getting a mark below 100 in math!

Input Specification

The first line of input will have the number of test cases, T. The next T lines will each contain a test case.

Each test case is one line with R and C separated by a single space.

Output Specification

For each test case, output the answer. Remember to take it modulo 10^9+7.

Constraints

There will be 5 subtasks each worth 20% of the points for this problem.

  • T \le 16; R \le 4; C \le 4
  • T \le 36; R \le 6; C \le 6
  • T \le 500; R \le 500; C \le 500
  • T \le 10; R \le 10^9; C \le 6
  • T \le 10; R \le 10^9; C \le 3\,000

In all subtasks, T, R, C \ge 1.

Tips

Optimize your program to run as fast as possible, even if you think it has the correct complexity.

Sample Input

4
1 1
2 2
2 3
3 2

Sample Output

1
7
25
25

Explanation

The seven matrices for the R = C = 2 case are:

11
11

11
10

11
01

10
11

01
11

01
10

10
01

Original Problem Author: No_stop; Problem Resource: HDU 5155


Comments


  • -1
    daoboyang41  commented on Aug. 10, 2018, 3:50 p.m. edited

    I wonder how this kid's math teacher's gene is passed on to the kid...

    Edit: Never mind. I only read the first paragraph when I wrote it.