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)
  }
}

import Data.Array (Ix, array, bounds, inRange, (!))
import Prelude hiding (Right)

data Direction = Neutral | Down | Right deriving (Eq, Ord, Ix)

paths :: Int -> Int -> Int -> Integer
paths m n k = go (1, 1, k, Neutral)
  where go (i, j, k, dir)
          | i == m && j == n = 1
          | otherwise = case dir of
            Neutral -> mod (get (i+1, j, k, Down) + get (i, j+1, k, Right)) (10^9 + 7)
            Down -> mod (get (i+1, j, k, Down) + get (i, j+1, k-1, Right)) (10^9 + 7)
            Right -> mod (get (i+1, j, k-1, Down) + get (i, j+1, k, Right)) (10^9 + 7)
        a = array ((1, 1, 0, Down), (m, n, k, Right))
            [(c, go c) | c <- (,,,) <$> [1..m] <*> [1..n] <*> [0..k] <*> [Down, Right]]
        get x | inRange (bounds a) x = a ! x
              | otherwise = 0
              
helper :: [String] -> Integer 
helper arr = do
    let new = map (read :: String -> Int) arr
    paths (new!!0) (new!!1) (new!!2)
    
main :: IO()
main = do
    raw <- getContents
    mapM_ print $ map helper $ tail $ map words $ lines raw