when not declared ATCODER_YULY3HEADER_HPP:
  const ATCODER_YULY3HEADER_HPP* = 1

  import
    algorithm,
    bitops,
    deques,
    heapqueue,
    math,
    macros,
    sets,
    sequtils,
    strformat,
    strutils,
    sugar,
    tables

  proc transLastStmt(n, res, bracketExpr: NimNode): (NimNode, NimNode, NimNode) =
    # Looks for the last statement of the last statement, etc...
    case n.kind
    of nnkIfExpr, nnkIfStmt, nnkTryStmt, nnkCaseStmt:
      result[0] = copyNimTree(n)
      result[1] = copyNimTree(n)
      result[2] = copyNimTree(n)
      for i in ord(n.kind == nnkCaseStmt)..<n.len:
        (result[0][i], result[1][^1], result[2][^1]) = transLastStmt(n[i], res, bracketExpr)
    of nnkStmtList, nnkStmtListExpr, nnkBlockStmt, nnkBlockExpr, nnkWhileStmt,
        nnkForStmt, nnkElifBranch, nnkElse, nnkElifExpr, nnkOfBranch, nnkExceptBranch:
      result[0] = copyNimTree(n)
      result[1] = copyNimTree(n)
      result[2] = copyNimTree(n)
      if n.len >= 1:
        (result[0][^1], result[1][^1], result[2][^1]) = transLastStmt(n[^1],
            res, bracketExpr)
    of nnkTableConstr:
      result[1] = n[0][0]
      result[2] = n[0][1]
      if bracketExpr.len == 1:
        bracketExpr.add([newCall(bindSym"typeof", newEmptyNode()), newCall(
            bindSym"typeof", newEmptyNode())])
      template adder(res, k, v) = res[k] = v
      result[0] = getAst(adder(res, n[0][0], n[0][1]))
    of nnkCurly:
      result[2] = n[0]
      if bracketExpr.len == 1:
        bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
      template adder(res, v) = res.incl(v)
      result[0] = getAst(adder(res, n[0]))
    else:
      result[2] = n
      if bracketExpr.len == 1:
        bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
      template adder(res, v) = res.add(v)
      result[0] = getAst(adder(res, n))

  macro collect*(init, body: untyped): untyped =
    runnableExamples:
      import sets, tables
      let data = @["bird", "word"]
      ## seq:
      let k = collect(newSeq):
        for i, d in data.pairs:
          if i mod 2 == 0: d
      assert k == @["bird"]
      ## seq with initialSize:
      let x = collect(newSeqOfCap(4)):
        for i, d in data.pairs:
          if i mod 2 == 0: d
      assert x == @["bird"]
      ## HashSet:
      let y = initHashSet.collect:
        for d in data.items: {d}
      assert y == data.toHashSet
      ## Table:
      let z = collect(initTable(2)):
        for i, d in data.pairs: {i: d}
      assert z == {0: "bird", 1: "word"}.toTable

    let res = genSym(nskVar, "collectResult")
    expectKind init, {nnkCall, nnkIdent, nnkSym}
    let bracketExpr = newTree(nnkBracketExpr,
      if init.kind == nnkCall: init[0] else: init)
    let (resBody, keyType, valueType) = transLastStmt(body, res, bracketExpr)
    if bracketExpr.len == 3:
      bracketExpr[1][1] = keyType
      bracketExpr[2][1] = valueType
    else:
      bracketExpr[1][1] = valueType
    let call = newTree(nnkCall, bracketExpr)
    if init.kind == nnkCall:
      for i in 1 ..< init.len:
        call.add init[i]
    result = newTree(nnkStmtListExpr, newVarStmt(res, call), resBody, res)

  proc nextString*(f: auto = stdin): string =
    var get = false
    result = ""
    while true:
      let c = f.readChar
      if c.int > ' '.int:
        get = true
        result.add(c)
      elif get: return
  proc nextInt*(f: auto = stdin): int = parseInt(f.nextString)
  proc nextFloat*(f: auto = stdin): float = parseFloat(f.nextString)

  proc chmax*[T](n: var T, m: T) {.inline.} = n = max(n, m)
  proc chmin*[T](n: var T, m: T) {.inline.} = n = min(n, m)
  proc `%=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = floorMod(n, m)
  proc `|=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n or m
  proc `&=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n and m
  proc `^=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n xor m
  proc `<<=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shl m
  proc `>>=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shr m

proc modPow*(a: int, k: Natural, MOD = 10^9 + 7): int =
  var
    a = a
    k = k
  result = 1
  while k > 0:
    if bitand(k, 1) == 1:
      result = floorMod(result*a, MOD)
    a = floorMod(a*a, MOD)
    k = k shr 1

proc modInv*(a: int, MOD = 10^9 + 7): int =
  return modPow(a, MOD - 2, MOD)

proc matVecMul*(A: seq[seq[int]], B: seq[int], MOD = 10^9 + 7): seq[int] =
  let N = B.len
  result = newSeq[int](N)
  for i in 0..<N:
    for j in 0..<N:
      result[i] = floorMod(result[i] + floorMod(A[i][j]*B[j], MOD), MOD)

proc matMul*(A, B: seq[seq[int]], M = 10^9 + 7): seq[seq[int]] =
  let
    N0 = A.len
    N1 = B[0].len
    N2 = A[0].len
  result = newSeqWith(N0, newSeq[int](N1))
  for i in 0..<N0:
    for j in 0..<N1:
      for k in 0..<N2:
        result[i][j] = floorMod(result[i][j] + A[i][k]*B[k][j], M)

proc matPow*(A: seq[seq[int]], K: Natural, M = 10^9 + 7): seq[seq[int]] =
  let N = len(A)
  var
    A = A
    K = K
  result = newSeqWith(N, newSeq[int](N))
  for i in 0..<N:
    result[i][i] = 1
  while K > 0:
    if bitand(K, 1) == 1:
      result = matMul(result, A, M)
    A = matMul(A, A, M)
    K = K shr 1

when isMainModule:
  const MOD = 10^9 + 7
  let C, N, M = nextInt()

  var mat = @[
    @[modInv(C), 0, 0, modInv(C)],
    @[0, modInv(C), (C - 1)*modInv(C) mod MOD, (C - 2)*modInv(C) mod MOD],
    @[1, 0, 0, 0],
    @[0, 1, 0, 0],
  ]
  var vec = matPow(mat, N).matVecMul(@[modInv(C), 0, 1, 0])
  var ans = floorMod(1 - vec[2], MOD).modPow(M)
  ans = floorMod(1 - ans, MOD)
  echo ans