405184: GYM101810 L Lazy Teacher

You are given a grid of desks consisting of n rows each of which is dived into m columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. Each desk is identified by a pair (x, y), which means that the desk is located in the row x and column y. There is a student sitting at each desk.

Today is the exam date! The teacher has prepared k forms of the exam with infinite copies of each form. The lazy teacher will give each student one form randomly with an equal probability.

Two students are considered to be adjacent if their desks share a common edge either vertically or horizontally. Your task is to count in how many ways the teacher can give the forms to the students so that no two adjacent students have the same form. Can you?

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

Each test case consists of a single line containing three integers n, m, and k (1 ≤ n ≤ 5, 1 ≤ m ≤ 10⁴, 1 ≤ k ≤ 10⁵), in which n and m are the number of rows and columns in the grid of desks, respectively, and k is the number of forms the teacher has prepared.

The sum of n × m overall test cases does not exceed 5 × 10⁵.

For each test case, print a single line containing the number of ways the teacher can give the forms to the students so that no two adjacent students have the same form module 10⁹ + 7.

2
5 1 2
3 7 2

2
2