import scala.io.StdIn
import scala.collection.mutable

object Solution {
  private abstract class Step(val direction: Byte) {
    def +(other: Step): Int = (this.direction ^ other.direction)
  }
  private object Step {
    case object Right extends Step(0)
    case object Down extends Step(1)
  }

  private final case class Cell(
      row: Int,
      col: Int
  ) {
    def -(step: Step): Cell = this.copy(
      row = row - (step.direction & 1),
      col = col - (step.direction ^ 1)
    )
  }

  private final case class State(
      turns: Int,
      last: Option[Step]
  ) {
    def +(step: Step): State = this.copy(
      turns = turns + last.map(_ + step).getOrElse(0),
      last = Option(step)
    )
  }

  private val startCell = Cell(1, 1)
  private val memo = mutable.Map[Cell, mutable.Map[State, BigInt]](
    startCell -> mutable.Map(
      State(0, None) -> 1
    )
  )

  def journey(n: Int, m: Int, k: Int): BigInt = {
    if ((k < 1) && (1 < n) && (1 < m))
      return 0
    val watson = Cell(n, m)
    if (!memo.contains(watson)) {
      (1 to n).foreach { row =>
        (1 to m).foreach { col =>
          val cell = Cell(row, col)
          if (!memo.contains(cell)) {
            memo.addOne(cell, mutable.Map.empty)
            if (1 < cell.col) {
              val leftCell = cell - Step.Right
              memo(leftCell).foreach { case (leftState, leftCount) =>
                val state = leftState + Step.Right
                val count = leftCount + memo(cell).getOrElse(state, 0)
                memo(cell)(state) = count
              }
            }
            if (1 < cell.row) {
              val upwardCell = cell - Step.Down
              memo(upwardCell).foreach { case (upwardState, upwardCount) =>
                val state = upwardState + Step.Down
                val count = upwardCount + memo(cell).getOrElse(state, 0)
                memo(cell)(state) = count
              }
            }
          }
        }
      }
    }
    val result = memo(watson)
      .filter(_._1.turns <= k)
      .values
      .sum
    result % (1e9 + 7).toInt
  }

  def main(args: Array[String]): Unit = {
    val in = Iterator
      .continually(StdIn.readLine())
      .takeWhile(null != _)
      .map(_.trim)
    val t = in.next().toInt
    (1 to t)
      .map(_ => in.next().split(' ').map(_.toInt))
      .map(nmk => journey(nmk.head, nmk.tail.head, nmk.last))
      .foreach(println)
  }
}