DMOPC '14 Exam Time P6 - Math Homework

View as PDF

Submit solution

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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.


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.


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

Sample Input

1 1
2 2
2 3
3 2

Sample Output



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








Original Problem Author: No_stop; Problem Resource: HDU 5155


  • 0
    daoboyang41  commented on Aug. 10, 2018, 11:50 a.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.

  • 0
    Cueball1234  commented on Sept. 3, 2017, 11:58 p.m. edit 2

    Internal Error?

  • -1
    awaykened  commented on Jan. 13, 2015, 5:25 p.m.

    my code works fine on my computer, and i expect it to at least run on the first subtask x.x is there a reason as to why the judge gives an error?

    • 1
      FatalEagle  commented on Jan. 13, 2015, 5:26 p.m.

      random is disallowed on PYPY. It might or might not be fixed soon.

      • -1
        awaykened  commented on Jan. 13, 2015, 5:27 p.m.

        crud, thanks :(

        • 1
          FatalEagle  commented on Jan. 13, 2015, 5:34 p.m.

          It has been fixed. Solutions were rejudged.