This page is still under construction.

Parts of this page are still being built. What you see may change.

Kings on a Chessboard

Time limit5sMemory limit256 MB

Summary
Count the ways to place k non-attacking kings on an x by y board and print each answer modulo 1,000,000,007.
Level

Medium7 of 10

Topics
Dynamic programming, Bit manipulation, Combinatorics
Solved
No attempts yet

Problem

You have a chessboard with xx rows and yy columns, and kk identical kings. Place all kk kings on the board so that no two of them attack each other. Two kings attack each other when they stand on adjacent squares horizontally, vertically, or diagonally. A square holds at most one king.

Write a program that counts the arrangements of the kk kings. The count can be very large, so report it modulo 1,000,000,007.

Input

The first line contains the number of test cases TT. Each of the next TT lines contains three integers xx, yy, and kk separated by one space.

  • 0<T≤500 < T \le 50
  • 2≤x,y≤152 \le x, y \le 15
  • 1≤k≤x×y1 \le k \le x \times y

Output

For each test case, print the number of arrangements modulo 1,000,000,007 on its own line, in the order the test cases are given.

Examples4

  1. Example 1

    Input
    4
8 8 1
7 7 16
7 7 7
3 7 15
    Expected output
    64
1
2484382
0

  2. Example 2

    Input
    6
2 2 1
2 2 2
2 2 3
2 2 4
2 3 2
3 3 4
    Expected output
    4
0
0
0
4
1

  3. Example 3

    Input
    4
2 2 1
15 15 1
7 11 1
3 14 1
    Expected output
    4
225
77
42

  4. Example 4

    Input
    5
5 5 5
6 6 9
4 7 6
8 8 16
10 10 20
    Expected output
    1974
3600
3698
281571
675251192